==Include(page="template/taskheader" task_id="asmax")==

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

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 distuncti $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 distincti $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 &le V~i~ ≤ 1000$

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

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

Exemple
 
 
|asmax.in |asmax.out |

h2. Exemplu

|5 |4 |
|-1 1 3 1 -1 | |
|4 1 | |
|1 3 | |
|1 2 | |
|4 5 | |

table(example). |_. asmax.in |_. asmax.out |
| 5
-1 1 3 1 -1
4 1
1 3
1 2
4 5 | 4 |
h3. Explicatie

Explicatie

Subarborele care contine varfurile 1,2,3 si 4 are suma 4.
==Include(page="template/taskfooter" task_id="asmax")==

481