G. Grabbing Goods
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are participating in the game show Bombastic Auction for Paired-up Contestants. You are facing a single opponent, and the goal for each of you is to win as much money as possible. There is a collection of $$$n$$$ goods indexed $$$1,\ldots,n$$$ that must be split between you and your opponent. The two of you alternate grabbing one of the goods at a time, with you going first. Each good $$$i$$$ has a value $$$a_i$$$ known to both of you, and after the goods are distributed, you each add up the values of your grabbed goods to determine how much money you end up winning.

The optimal strategy for this game used to be incredibly simple: always grab the remaining good with the highest value. Critics were already referring to the show as the Boring Auction for Pinheaded Children. For this edition, the hosts have thus decided to change the rules so that the old strategy is no longer viable.

In the new edition, the goods are laid out in a formation so that they form the vertices of a rooted tree. Good $$$1$$$ is at the root of the tree, and all the remaining goods $$$i$$$ have a unique parent good $$$p_i \lt i$$$. Following the parent sequence of any good always leads to the root; there are no cycles. The new rule then states that you may only ever grab either the root, or a good whose parent has already been grabbed.

Under the new rule, this means that the first grabbed good must always be the good at the root of the tree. However, if any good had the root as its parent, then that good effectively becomes a new root of a new smaller tree. This means that the goods are always distributed among a number of disjoint rooted trees, and you must always grab the good at the root of one of the trees, splitting up the rest of that tree into a number of new disjoint rooted trees.

Both you and your opponent aim to maximize the amount of money you end up winning. With you grabbing the first good, and with both you and your opponent playing optimally, how much money do you end up winning?

Illustration for the first two samples. With both players playing optimally, you get the goods in the yellow vertices and your opponent gets the goods in the blue vertices.
Input

The input consists of:

  • One line with an integer $$$n$$$ ($$$2 \leq n \leq {10^5}$$$), the number of goods.
  • One line with $$$n$$$ integers $$$a_1,\ldots,a_n$$$ ($$$0 \leq a_i \leq {10^9}$$$ for each $$$i$$$), the value of each good.
  • One line with $$$n-1$$$ integers $$$p_2,\dots,p_n$$$ ($$$1 \leq p_i \lt i$$$ for each $$$i$$$), where $$$p_i$$$ is the index of the parent of good $$$i$$$. Recall that good $$$1$$$ is at the root.
Output

Output the amount of money that you end up winning (the sum of the values of your grabbed goods) if both you and your opponent play optimally.

Examples
Input
7
1 5 11 6 2 4 3
1 2 3 1 5 6
Output
16
Input
7
1 5 11 9 2 4 3
1 2 3 1 5 6
Output
17
Input
4
3 6 9 4
1 2 1
Output
9
Input
6
0 2 9 1 6 3
1 2 1 4 4
Output
8