P9133 [THUPC 2023 Preliminary] Monopoly.

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

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

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

One line contains one integer, which is the answer.

#### 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 . Translated by ChatGPT 5