Echidistant

Time limit: 2s Memory limit: 512MB Input: echidistant.in Output: echidistant.out

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 AA 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 11 este echidistant:

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

, deoarece distanțele de la nodul 11 la nodurile 44, 55, 66 nu sunt toate egale.

Valoarea unui arbore. Considerăm un arbore AA cu nodurile numerotate cu 1,,N1, \ldots, N, unde fiecare nod i=1,,Ni = 1, \ldots, N are o greutate w(i)w(i) (aceasta putând fi și negativă). Valoarea arborelui AA, notată cu val(A)\text{val}(A), se definește în modul următor. Considerăm oricare mod de a elimina succesiv frunze ale arborelui AA î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 x1,,xkx_1, \ldots, x_k nodurile rămase după această eliminare. Valoarea val(A)\text{val}(A) a lui AA este suma maximă w(x1)++w(xk)w(x_1) + \ldots + w(x_k) posibilă pentru oricare mod de a elimina frunze din AA.

De exemplu, să considerăm cel de-al doilea arbore de mai sus (cel cu 66 noduri). Câteva din mulțimile de noduri ce pot rămâne după eliminări sunt {1,2,3,5,6}\{1, 2, 3, 5, 6\} (eliminăm nodul 44), {1,2,3,4}\{1, 2, 3, 4\} (eliminăm nodurile 55, 66), {1,2}\{1, 2\} (eliminăm nodurile 44, 55, 66, 33 în această ordine), și {1}\{1\} (eliminăm nodurile 44, 55, 66, 33, 22, în această ordine). Dacă atribuim acestui arbore greutățile w(1),,w(6)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))\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 AA cu NN noduri înrădăcinat în nodul 11, și cu greutățile w(1),,w(N)w(1), \ldots, w(N). Fie AiA_i subarborele lui AA înrădăcinat în nodul ii. Să se calculeze val(A1),,val(AN)\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 NN de noduri ale arborelui AA. Pe al doilea rând se găsesc numerele w(1),,w(N)w(1), \ldots, w(N) în ordine, separate cu spații. Pe al treilea rând se găsesc N1N − 1 numere t(2),,t(N)t(2), \ldots, t(N), ce reprezintă faptul că muchiile arborelui sunt 2t(2)2 − t(2), 3t(3)3 − t(3), \ldots, Nt(N)N − t(N).

Date de ieșire

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

Restricții și precizări

  • 1N1 000 0001 \leq N \leq 1 \ 000 \ 000
  • 1 000 000 000w(i)1 000 000 000−1 \ 000 \ 000 \ 000 \leq w(i) \leq 1 \ 000 \ 000 \ 000 pentru 1iN1 \leq i \leq N
  • 1t(i)N1 \leq t(i) \leq N pentru 1iN1 \leq i \leq N
# Punctaj Restricții
1 9 t(i)=i1t(i) = i − 1 pentru 2iN2 \leq i \leq N
2 12 1N1001 \leq N \leq 100
3 21 1N5 0001 \leq N \leq 5 \ 000
4 44 1N100 0001 \leq N \leq 100 \ 000
5 14 Fără restricții suplimentare

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 66 noduri, unde atribuim greutățile [0,10,10,1,1,1][0, -10, 10, 1, -1, -1] la nodurile [1,2,3,4,5,6][1, 2, 3, 4, 5, 6].

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