Arbore9

arbore9

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

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$.

Poveste şi cerinţă...

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: u{~i~}, v{~i~}, a{~i~}, b{~i~}.

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

h2. Date de ieşire

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

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

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

* $-1 000 000 000 ≤ a{~i~}, b{~i~} ≤ 1 000 000 000$

* Pentru $30$ de puncte, $1 ≤ N ≤ 1000$

* 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 |

| 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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
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") ==