Concurs Albinuta-GP pt elevi | sumsubsum

Cerință

Se dă un arbore cu $n$ noduri, fiecare nod având o valoare notată pe el. Rădăcina arborelui este nodul $1$. Să se afle suma sumelor subarborilor arborelui dat.

Un subarbore este definit ca fiind un arbore cu rădăcina în nodul $i$ și care cuprinde toate nodurile la care se poate ajunge din nodul $i$, dacă tăiem legătura dintre $i$ și părintele său.

De remarcat că subarborele nodului $1$ este identic cu arborele dat.

Date de intrare

Pe prima linie se va afla $n$, numărul de noduri din arbore.

Pe cea de-a doua linie se vor afla $n$ valori, reprezentând valorile nodurilor din arbore.

Pe următoarele $n - 1$ linii se vor afla muchiile arborelui, muchia $(x, y)$ semnificând faptul că există muchie între nodurile $x$ și $y$.

Date de ieșire

Pe prima linie se va afișa răspunsul cerut.

Restricții și precizări

• $1 \leq n \leq 2 \cdot 10^5$.
• $1 \leq v_i \leq 10^6$.

Exemplu

stdin

5
5 1 8 3 4
1 2
1 3
2 4
4 5

stdout

48

Explicație

De exemplu, subarborele nodului $2$ include nodurile $2$, $4$ si $5$. Suma acestori valori este $1 + 3 + 4 = 8$.