Se consideră un arbore cu n noduri numerotate de la 1 la n. Se stie că rădăcina arborelui este nodul 1. Fiecare nod i are asociat un număr natural nenul vi.
Cerinţă
Să se determine suma maximă care se poate obtine alegând în mod convenabil o submultime de noduri, astfel încât dacă este ales un nod i, în submultime nu poate fi nici nodul tată al lui i, nici eventualii fii ai lui i.
Date de intrare
Fişierul de intrare arbsum.in conţine pe prima linie numărul n. Pe a doua linie, separate prin câte un spatiu, se află numerele naturale t1,t2,...,tn, în care tireprezintă nodul tată al nodului i. Pentru că 1 este rădăcina arborelui, atunci întotdeauna t1=0. Pe a treia linie, separate prin câte un spatiu, se află numerele naturale v1,v2,...,vn, unde vi este valoarea asociată nodului i.
Date de ieşire
Fişierul de ieşire arbsum.out va conţine pe prima linie un singur număr natural reprezentând suma maximă posibilă.
Restricţii
3 <= n <= 100 000
1 <= vi <= 1000
Pentru 50% din teste, n <= 1000
Exemplu
arbsum.in
arbsum.out
Explicaţii
5
0 1 1 3 3
3 4 4 5 3
12
Arborele are 5 noduri. Nodurile 2 şi 3 au ca nod tată pe 1, iar nodurile 4 şi 5 au ca tată pe 3. Nodul 1 are asociată valoarea 3, nodurile 2 şi 3 au asociată valoarea 4, nodul 4 are asociată valoarea 5, iar nodul 5 are valoarea 3 asociată.
Obţinem suma maximă 12 dacă se aleg nodurile 2, 4, 5: v2+v4+v5=4+5+3=12