==Include(page="template/raw")==

(Arbore de Suma Maxima)
 

Se considera un arbore (graf neorientat, conex si aciclic) cu $N$ varfuri, in care fiecare varf $i$ are asociata o valoarea intreaga $V~i~$. Se defineste un subarbore al arborelui dat, ca fiind un subgraf conex nevid al acestuia (care poate coincide chiar cu arborele dat).
h2. Cerinta

h2. Date de Intrare

Prima linie a fisierului de intrare $asmax.in$ contine numarul intreg $N$, reprezentand numarul de varfuri ale arborelui. A doua linie a fisierului contine $N$ valori intregi, reprezentand valorile asociate nodurilor. A $i$-a valoare din acest sir reprezinta valoarea asociata nodului $i$. Urmatoarele $N-1$ linii contin cate doi intregi distincti $a$ si $b$, separati printr-un spatiu, avand semnificatia ca exista muchie intre varful numerotat cu a si cel numerotat cu $b$.

Prima linie a fisierului de intrare $asmax.in$ contine numarul intreg $N$, reprezentand numarul de varfuri ale arborelui. A doua linie a fisierului contine $N$ valori intregi, reprezentand valorile asociate nodurilor. A $i$-a valoare din acest sir reprezinta valoarea asociata nodului $i$. Urmatoarele $N-1$ linii contin cate doi intregi distuncti $a$ si $b$, separati printr-un spatiu, avand semnificatia ca exista muchie intre varful numerotat cu a si cel numerotat cu $b$.

h2. Date de Iesire

h2. Restrictii
* $1 ≤ N ≤ 16.000$

* $-1000 ≤ V~i~ ≤ 1000$

* $-1000 &le V~i~ ≤ 1000$

* Varfurile sunt numerotate cu numere distincte intre 1 si $N$

h2. Exemplu

Exemple
 

|asmax.in |asmax.out |