== 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$ ...
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
În fişierul de ieşire $arbore9.out$ ...
În fişierul de ieşire $arbore9.out$ se vor afişa, pe o singură linie, $N$ numere separate prin câte un spaţiu, al $i$-lea număr reprezentând costul maxim obţinut plecând din nodul $i$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $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$
h2. Exemplu
table(example). |_. arbore9.in |_. arbore9.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 8
1 2 2 2
2 3 0 -5
2 4 -1 3
4 5 5 2
4 6 4 2
1 7 3 1
7 8 -1 -3
| 12 12 10 12 12 12 12 11
|
h3. Explicaţie
...
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") ==
