McArbore

Cerință

Se dau $n$, un șir de $n$ elemente $c$ și un arbore cu $n$ noduri, înrădăcinat în nodul $1$. Există un șir ascuns $a$ de $n$ elemente.

Definim o operație "adună" pe un nod $u$ astfel:

• Fie $S$ mulțimea tuturor frunzelor din subarborele lui $u$;
• Veți alege un $x$, iar pentru toți $v \in S$, se va face operația $a_v = a_v + x$;

Operația "adună" se poate face doar pe un nod "activ".

Definim costul unui șir astfel:

• Inițial, $cost = 0$;
• Pentru fiecare nod $i$ pe care vrem să îl activăm, $cost = cost + c_i$;
• Costul final va fi $cost$;

De exemplu, pentru un arbore cu $4$ noduri, având muchiile 1 2, 2 3 și 2 4, șirul $c = [4, 17, 9, 3]$ și șirul $a = [4, 9, 3, 3]$, dacă adăugăm la cost $4$ pentru a activa nodul $1$, la frunzele $3$ și $4$ putem adăuga -2 la $a_3$ și $a_4$, apoi -1, șirul final $a$ fiind $[4, 9, 0, 0]$.

Care este costul minim pe care îl putem obține astfel încât pentru orice șir $a$, după ce aplicăm niște operații "aduna", pentru orice frunză $u$ avem $a_u = 0$, dacă inițial toate nodurile sunt inactive?

Date de intrare

Pe prima linie se va găsi numărul natural $n$. Pe doua linie se vor afla $n$ numere naturale, a $i$-a valoare reprezentând $c_i$, pentru $1 \leq i \leq n$. Pe următoarele $n-1$ linii se vor afla muchiile arborelui.

Dacă folosiți citire cu std::cin, vă recomandăm să adăugați aceste linii la începutul programului:

std::ios_base::sync_with_stdio(0);
std::cin.tie(0);

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, costul minim.

Restricții și precizări

• $2 \leq n \leq 1 \ 000 \ 000$;
• $1 \leq c_i \leq 10^9$, pentru $1 \leq i \leq n$;

Exemplul 1

stdin

6
1 10 6 9 2 3
1 2
1 3
1 4
3 5
3 6

stdout

15

Explicație

Se vor activa nodurile $1, 4, 5, 6$. Dacă ar fi activate doar nodurile $1, 5, 6$, atunci pentru șirul $a = [100, 100, 100, 101, 100, 100]$, nu se poate ajunge în același timp la valori nule pe pozițiile $2$, respectiv $4$.

Exemplul 2

stdin

6
1 10 2 9 2 3
1 2
1 3
1 4
3 5
3 6

stdout

14

Explicație

Se vor activa nodurile $1, 3, 4, 5$.