Echidistant

Iaroslav-Menelaos Trapanache, zis Trăsnetul Dunării de Jos, sau (din partea apropiaților) Faraonu’, vrea să devină mai înțelept, și are chef să rezolve o problemă de informatică cu arbori la fel de echidistanți și corecți ca el, așa că a compus următoarea problemă.

Arbore echidistant. Un arbore înrădăcinat $A$ se numește echidistant dacă toate frunzele lui sunt la aceeași distanță față de rădăcină. (Reținem că distanța dintre două noduri este dată de numărul de muchii al lanțului elementar unic dintre cele două noduri.)

De exemplu, următorul arbore înrădăcinat în nodul $1$ este echidistant:

, pe când următorul (înrădăcinat tot în nodul $1$) nu este echidistant:

, deoarece distanțele de la nodul $1$ la nodurile $4$, $5$, $6$ nu sunt toate egale.

Valoarea unui arbore. Considerăm un arbore $A$ cu nodurile numerotate cu $1, \ldots, N$, unde fiecare nod $i = 1, \ldots, N$ are o greutate $w(i)$ (aceasta putând fi și negativă). Valoarea arborelui $A$, notată cu $\text{val}(A)$, se definește în modul următor. Considerăm oricare mod de a elimina succesiv frunze ale arborelui $A$ în urma căruia arborele devine sau rămâne echidistant, păstrând nodul rădăcină. (Putem elimina un nod care devine frunză în urma eliminării altor noduri.) Fie $x_1, \ldots, x_k$ nodurile rămase după această eliminare. Valoarea $\text{val}(A)$ a lui $A$ este suma maximă $w(x_1) + \ldots + w(x_k)$ posibilă pentru oricare mod de a elimina frunze din $A$.

De exemplu, să considerăm cel de-al doilea arbore de mai sus (cel cu $6$ noduri). Câteva din mulțimile de noduri ce pot rămâne după eliminări sunt $\{1, 2, 3, 5, 6\}$ (eliminăm nodul $4$), $\{1, 2, 3, 4\}$ (eliminăm nodurile $5$, $6$), $\{1, 2\}$ (eliminăm nodurile $4$, $5$, $6$, $3$ în această ordine), și $\{1\}$ (eliminăm nodurile $4$, $5$, $6$, $3$, $2$, în această ordine). Dacă atribuim acestui arbore greutățile $w(1), \ldots, w(6)$, atunci valoarea lui este: $\max(w(1) + w(2) + w(3) + w(5) + w(6),\ w(1) + w(2) + w(3) + w(4),\ w(1) + w(2),\ w(1))$.

Cerință

Se dă un arbore $A$ cu $N$ noduri înrădăcinat în nodul $1$, și cu greutățile $w(1), \ldots, w(N)$. Fie $A_i$ subarborele lui $A$ înrădăcinat în nodul $i$. Să se calculeze $\text{val}(A_1), \ldots, \text{val}(A_N)$.

Date de intrare

Pe primul rând al fișierului de intrare echidistant.in se găsește numărul $N$ de noduri ale arborelui $A$. Pe al doilea rând se găsesc numerele $w(1), \ldots, w(N)$ în ordine, separate cu spații. Pe al treilea rând se găsesc $N − 1$ numere $t(2), \ldots, t(N)$, ce reprezintă faptul că muchiile arborelui sunt $2 − t(2)$, $3 − t(3)$, $\ldots$, $N − t(N)$.

Date de ieșire

Unicul rând din fișierul de ieșire echidistant.out conține $N$ numere, mai exact $\text{val}(A_1), \ldots, \text{val}(A_N)$ separate prin spații, în această ordine.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• $−1 \ 000 \ 000 \ 000 \leq w(i) \leq 1 \ 000 \ 000 \ 000$ pentru $1 \leq i \leq N$
• $1 \leq t(i) \leq N$ pentru $1 \leq i \leq N$

Exemplu

echidistant.in

6
0 -10 10 1 -1 -1
1 2 2 3 3

echidistant.out

1 1 10 1 -1 -1

Explicație

Acesta este cel de-al doilea arbore din enunț, cel cu $6$ noduri, unde atribuim greutățile $[0, -10, 10, 1, -1, -1]$ la nodurile $[1, 2, 3, 4, 5, 6]$.