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

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

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

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

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

h3. Explicatie

Explicatie

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

481