Povišica

Zaposleni v podjetju so organizirani v hierarhično vodstveno strukturo. Zaradi enostavnosti bomo zaposlene osebe naslavljali kar s celimi števili od $1$ do $N$, kolikor je zaposlenih v podjetju. Vsaka oseba ima sebi neposredno nadrejeno osebo $a_i$, razen nekaterih, ki predstavljajo vrh hierarhije in nimajo nadrejene osebe. Oseba in njej neposredno ter posredno podrejene osebe predstavljajo oddelek v tej hierarhiji. Ob začetku poslovnega leta je vsak oddelek prejel povišico $p_i$, kar pomeni, da vsi v oddelku $i$ (oseba $i$ ter njej neposredno in posredno podrejene osebe) prejmejo povišico $p_i$. Ker so zaposleni del več oddelkov (imajo več nadrejenih, od katerih si je vsak izboril neko povišico za svoj oddelek), so deležni več povišic. Izračunajte, kakšno skupno povišico bo dobil vsak zaposleni.

Omejitve podatkov:

• $1 \leq N \leq 10^5$
• $0 \leq p_i \leq 1000$

Vhodni in izhodni podatki:

Prva vrstica vsebuje število zaposlenih $N$. Druga vrstica vsebuje $N$ števil $a_i$, kjer $i$-to število opisuje osebo $i$ s številom $a_i$, ki predstavlja številko njej neposredno nadrejene osebe. Vrednost $p_i=0$ pomeni, da oseba nima nadrejenega. Tretja vrstica podaja na enak način povišice $d_i$ oddelkov, ki jih vodi oseba $i$ .

Izpišite vrstico z $N$ števili, kjer naj $i$-to število predstavlja skupno povišico osebe $i$.

Primer vhoda:

11
5 3 0 5 0 10 3 3 7 7 1
0 5 2 2 1 3 1 1 0 4 1

Pravilen izhod:

1 7 2 3 1 10 3 3 3 7 2

Oseba 6 je prejela za svoj oddelek povišico $3$, njej nadrejena oseba 10 je zagotovila povišico $4$, oseba 7 je za svoj oddelek prejela povišico $1$ in oseba 3 povišico $2$, kar za osebo 6 skupaj znese $3+4+1+2=10$.