sumsubsum

Time limit: 0.5s Memory limit: 64MB Input: Output:

Cerință

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

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

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

Date de intrare

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

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

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

Date de ieșire

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

Restricții și precizări

  • 1n21051 \leq n \leq 2 \cdot 10^5.
  • 1vi1061 \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 22 include nodurile 22, 44 si 55. Suma acestori valori este 1+3+4=81 + 3 + 4 = 8.

Log in or sign up to be able to send submissions!