Background

One day, Xiao W and Xiao H are playing Monopoly.

Problem Description

The rules of this version of Monopoly are quite special. Its map is a rooted tree with $n$ nodes, where node $1$ is the root. Each node on the tree has a price, and the price of node $x$ is denoted as $w_x$.

For two different nodes $x, y$ on the tree, if $x$ is an ancestor of $y$ (that is, $x$ lies on the simple path from node $1$ to node $y$), then we say that $x$ dominates $y$.

During the game, Xiao W and Xiao H take turns to buy an unbought node on the tree, until all $n$ nodes have been bought by either Xiao W or Xiao H. (Before the game starts, all nodes on the tree are unbought.)

For a purchase, suppose the buyer purchases node $x$. First, they must pay $w_x$ game coins to the system. At this time, suppose $x$ dominates $n_1$ nodes that have already been bought by the buyer's opponent, and meanwhile $x$ is dominated by $n_2$ nodes that have already been bought by the opponent. If $n_1 > n_2$, then the opponent must pay $n_1 - n_2$ game coins to the buyer; if $n_1 < n_2$, then the buyer must pay $n_2 - n_1$ game coins to the opponent.

Both Xiao W and Xiao H are extremely smart. They will both use optimal strategies in the game to earn as many game coins as possible. Now Xiao W wants to test you: if he moves first, how many game coins can he finally earn? (That is, during the whole game, the number of game coins Xiao W receives from Xiao H minus the number of game coins he pays to the system and to Xiao H. You may assume that before the game starts, both Xiao W and Xiao H have enough game coins. Note that the answer may be negative.)

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ non-negative integers, where the $i$-th integer is the price $w_i$ of node $i$.

The third line contains $n - 1$ positive integers, where the $i$-th positive integer denotes the parent index of node $i + 1$.

Output Format

One line contains one integer, which is the answer.

7
0 0 1 0 0 0 0
1 1 2 2 3 3

2

见附件中的 2.in

见附件中的 2.ans

Hint

Sample Explanation 1

One possible game process is:

• First purchase: Xiao W buys node $1$ and pays $0$ game coins to the system.
• Second purchase: Xiao H buys node $2$, pays $0$ game coins to the system, and pays $1$ game coin to Xiao W.
• Third purchase: Xiao W buys node $3$ and pays $1$ game coin to the system.
• Fourth purchase: Xiao H buys node $4$, pays $0$ game coins to the system, and pays $1$ game coin to Xiao W.
• Fifth purchase: Xiao W buys node $6$ and pays $0$ game coins to the system.
• Sixth purchase: Xiao H buys node $5$, pays $0$ game coins to the system, and pays $1$ game coin to Xiao W.
• Seventh purchase: Xiao W buys node $7$ and pays $0$ game coins to the system.

Subtasks

For all testdata, $1 \leq n \leq 2 \times 10^5$, $0 \leq w_x \leq 2 \times 10^5$. It is guaranteed that the input graph is a rooted tree with node $1$ as the root.

Source

From the preliminary round of the 2023 Tsinghua University Student Programming Contest and Collegiate Invitational Contest (THUPC2023).

Resources such as editorials can be found at https://github.com/THUSAAC/THUPC2023-Pre.

Translated by ChatGPT 5