P8294 [NOI Qualifier Joint Contest 2022] Maximum Weight Independent Set Problem

Little E likes to create maximum weight independent set problems. Next, he came up with $n$ maximum weight independent set problems. Little E has $n$ AIs, numbered $1 \sim n$. At the beginning, the $i$-th AI stores $d_i$ maximum weight independent set problems that Little E prepared in advance. Some AIs can communicate with each other. For all $2 \le i \le n$, the $i$-th AI can communicate with the $c_i$-th AI. Here $c_i < i$, and the same value of $c_i$ appears no more than $2$ times. Therefore, these AIs form a binary tree. Besides these, no other pairs of AIs can communicate. Little E needs to temporarily disconnect the connections among these AIs. He can only disconnect the connections one by one. Before disconnecting the connection between two AIs that can communicate, they will exchange all problems stored inside them; see the sample for details. Little E wants the total number of problems involved in exchanges to be as small as possible after all connections are disconnected. He asks you to solve this problem, and says that if you succeed, then when creating those maximum weight independent set problems, he will help you submit a reference solution code.

The first line contains a positive integer $n$. The second line contains $n$ integers; the $i$-th one is $d_i$. The third line contains $n - 1$ positive integers; the $i$-th one is $c_{i+1}$.

Output one integer in a single line, representing the answer.

**[Sample Explanation #1]** One optimal plan is: disconnect the connection between AI $1$ and AI $2$. Then they need to exchange $2 + 1 = 3$ problems. Then disconnect the connection between AI $1$ and AI $3$. Then they need to exchange $1 + 3 = 4$ problems. So the answer is $7$. **[Constraints]** It is guaranteed that $1 \le c_i \le i$, and the same value of $c_i$ appears at most twice. It is guaranteed that $1 \le d_i \le {10}^9$. | Test Point ID | $n \leq$ | |:-:|:-:| | $1 \sim 3$ | $10$ | | $4 \sim 7$ | $100$ | | $8 \sim 11$ | $500$ | | $12 \sim 16$ | $1000$ | | $17 \sim 25$ | $5000$ | Translated by ChatGPT 5