arbore9

Arbore9

== include(page="template/taskheader" task_id="arbore9") ==

Poveste şi cerinţă...

X vrea să facă o excursie într-un oraş în formă de arbore cu $N$ noduri. Pentru fiecare muchie de la $u$ la $v$ se cunosc coeficientul de frumuseţe $a$ al parcurgerii muchiei de la $u$ la $v$ şi coeficientul de frumuseţe $b$ al parcurgerii muchiei de la $v$ la $u$ ( $a$ şi $b$ numere întregi). X poate merge oricum pe muchiile arborelui, însă la final îşi va aduce aminte numai ultima dată când a vizitat o muchie. Coeficientul total este suma coeficienţilor muchiilor pe care X îşi aminteşte că le-a vizitat. Pentru a se hotărî din ce nod să înceapă excursia, X te roagă să afli coeficientul total maxim care se poate obţine plecând din fiecare nod din cele $N$.

h2. Date de intrare

Fişierul de intrare $arbore9.in$ conţine pe prima linie numărul $N$ de noduri ale arborelui. Următoarele $N-1$ vor conţine cate $4$ numere reprezentând o muchie: x{~i~}, y{~i~}, a{~i~}, b{~i~}, unde x{~i~} şi y{~i~} sunt nodurile, a{~i~} reprezintă costul parcurgerii muchiei de la $x$ la $y$ şi b{~i~} reprezintă costul parcurgerii muchiei de la $y$ la $x$.

Fişierul de intrare $arbore9.in$ conţine pe prima linie numărul $N$ de noduri ale arborelui. Următoarele $N-1$ vor conţine cate $4$ numere reprezentând o muchie: u{~i~}, v{~i~}, a{~i~}, b{~i~}.

h2. Date de ieşire

h2. Restricţii
* $1 ≤ N ≤ 100 000$

* $1 ≤ x{~i~}, y{~i~} ≤ N$

* $1 ≤ u{~i~}, v{~i~} ≤ N$

* $-1 000 000 000 ≤ a{~i~}, b{~i~} ≤ 1 000 000 000$
* Pentru $30$ de puncte, $1 ≤ N ≤ 1000$
* Pentru alte $20$ de puncte, $0 ≤ a{~i~}, b{~i~} ≤ 1 000 000 000$

h3. Explicaţie

Plecând din nodul $1$, un drum de coeficient total maxim este: 1 -> 7 -> 1 -> **7 -> 1 -> 2 -> 4** -> 6 -> 4 -> 5

Plecând din nodul $1$, un drum de coeficient total maxim este: 1 -> 2 -> 4 -> **5 -> 4** -> **6 -> 4 -> 2 -> 1** -> 7 -> **1 -> 7** Doar coeficientul muchiilor îngroşate va fi adunat la coeficientul total.

== include(page="template/taskfooter" task_id="arbore9") ==