- Time limit: 2.00 s
- Memory limit: 512 MB
Uolevin sedän yritys on kasvanut vuosien aikana, ja nyt yrityksen palveluksessa on suuri määrä työntekijöitä. Tämän vuoksi Uolevin setä järjestää yt-neuvottelut. Uolevin setä ajattelee, että työntekijälle voidaan antaa potkut jos hänen esimiehelleen ei anneta potkuja. Tiedät jokaisen yrityksen työntekijän palkan ja esimiehen. Mikä on suurin mahdollinen erotettujen työntekijöiden palkkojen summa?
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku n: työntekijöiden määrä. Työntekijät on numeroitu 1,2,\ldots,n, ja työntekijä 1 on Uolevin setä (yrityksen johtaja).
Syötteen toisella rivillä on n lukua, p_1, p_2, \ldots, p_n, jokaisen työntekijän palkka. Yllättävää kyllä työntekijällä voi olla suurempi palkka kuin hänen esimiehellään.
Sitten syötteessä on n-1 lukua, jotka kertovat, kuka on kunkin työntekijän esimies. Ensin tulee työntekijä 2:n esimies, sitten työntekijä 3:n esimies jne. työntekijään n asti. Uolevin sedällä ei ole esimiestä.
Tuloste
Ohjelmasi tulee tulostaa suurin mahdollinen erotettujen työntekijöiden palkkojen summa. Huomaa että myös Uolevin setä voidaan erottaa.
Rajat
- 1 \le n \le 10^5
- 1 \le p_i \le 10^9
Esimerkki
Syöte:
5 3 2 3 1 1 1 1 3 3
Tuloste:
5
Syöte:
5 1 1 1 1 1 1 2 3 1
Tuloste:
3
Syöte:
5 1 1 2 2 2 1 2 2 1
Tuloste:
6