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 $b$ la $a$ ( $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$.

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

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** Doar coeficientul muchiilor îngroşate va fi adunat la coeficientul total.

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