407936: GYM102946 C Chicken Nuggets

Carl the shark goes to his favorite restaurant for dinner. There is a special event happening today: if he plays and wins a game, the restaurant will offer free chicken nuggets as prize!

The game is set up as follows:

1. First, the restaurant manager arranges $$$n$$$ plates in a row. They are numbered from 1 to $$$n$$$.
2. For $$$i = 2, 3, \dots, n$$$, the manager chooses an integer $$$a_i$$$ such that $$$1 \le a_i \le i - 1$$$, and connects plate $$$i$$$ and plate $$$a_i$$$ with a single strand of spaghetti (it is attached to both plates).
3. For $$$i = 1, 2, \dots, n$$$, the manager chooses a positive integer $$$c_i$$$, and places $$$c_i$$$ chicken nuggets on plate $$$i$$$.

Then, the game is played by one player. The player should do the following:

1. They select a set of plates, and remove all the selected plates. It is possible to select zero or all plates.
2. For each spaghetti strand, if it was attached to a plate that was removed, then the strand is removed as well.
3. For each remaining plate, they count the number of remaining spaghetti strands attached to it. If it is an even number, then the game is lost and the player receives nothing.
4. Otherwise, if the game isn't lost, then the player wins and receives all chicken nuggets on the remaining plates as prize.

Carl has a chance to play the game. Since chicken nuggets are his favorite food, he wishes to get as many chicken nuggets as possible. However, the number of plates is so large that he can't possibly calculate the result of the game. Can you help him out?

The first line consists of one integer $$$n$$$. The second line contains $$$n - 1$$$ integers $$$a_2, a_3, \dots, a_n$$$. The third line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$.

Technical specification:

• $$$2 \le n \le 2 \times 10^5$$$
• $$$1 \le a_i \le i - 1$$$ for $$$i = 2, 3, \dots, n$$$
• $$$1 \le c_i \le 10^4$$$ for $$$i = 1, 2, \dots, n$$$

Print one integer, the maximum amount of chicken nuggets Carl can receive from the game.

3
1 1
3 6 5

9

4
1 2 2
5 6 7 8

26