asmax (arbore de suma maxima)

Se considera un arbore (graf neorientat, conex si aciclic) cu N vârfuri, în care fiecare vârf i are asociata o valoarea întreaga V_i. Se defineste un subarbore al arborelui dat, ca fiind un subgraf conex nevid al acestuia (care poate coincide chiar cu arborele dat).

Cerinta

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 distuncti a si 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 <= V_i <= 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.