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 v_i.

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 t₁,t₂,...,t_n, în care t_i reprezintă nodul tată al nodului i. Pentru că 1 este rădăcina arborelui, atunci întotdeauna t₁=0. Pe a treia linie, separate prin câte un spatiu, se află numerele naturale v₁,v₂,...,v_n, unde v_i 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 <= v_i <= 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

prof. Dan Pracsiu

Liceul "Stefan Procopiu" Vaslui

dpracsiu@yahoo.com