Se considera un arbore (graf neorientat, conex si aciclic) cu N vârfuri,
în care fiecare vârf i are asociata o valoarea întreaga Vi.
Se defineste un subarbore al arborelui dat, ca fiind un subgraf conex nevid
al acestuia (care poate coincide chiar cu arborele dat).
Cerinta
Se cere sa determinati un subarbore al unui arbore dat, pentru care suma valorilor
asociate vârfurilor continute în subarbore sa fie maxima.
Date de intrare
Prima linie a fisierului de intrare asmax.in
contine numarul întreg N, reprezentând numarul de vârfuri
ale arborelui. A doua linie a fisierului contine N valori întregi, reprezentând
valorile asociate nodurilor. A i-a valoare din acest sir reprezinta valoarea
asociata nodului i. Urmatoarele N-1 linii contin câte doi întregi
distincti a b, separati printr-un spatiu, având semnificatia ca exista
muchie între vârful numerotat cu a si cel numerotat cu b.
Date de iesire
În fisierul asmax.out
veti afisa suma maxima a unui subarbore al arborelui dat.
Restrictii
1 <= N <= 16 000
-1000 <= Vi <= 1000
Vârfurile sunt numerotate cu numere distincte între 1 si N.
40% din testele folosite la evaluare vor avea N<=15
Exemple
asmax.in
asmax.out
5
-1 1 3 1 -1
4 1
1 3
1 2
4 5
4
Explicatie
Subarborele care contine vârfurile 1, 2, 3 si 4 are suma 4.
Mugurel Andreica
Universitatea Politehnica Bucuresti