Minimizing Total Exchange in Disconnected AI Trees

We are given a tree of $n$ AIs (numbered $1$ to $n$). Initially the $i$‐th AI holds $d_i$ problems. For every $2\le i\le n$, the $i$-th AI can communicate with the $c_i$-th AI ($c_i < i$). (Moreover, the same $c_i$ appears at most twice, so the communication network forms a binary tree.)\n\nBefore disconnecting any connection, the two AIs that can communicate will exchange all the problems they currently hold. Since the connections must be disconnected one by one, the order in which the connections are disconnected affects the total number of times problems participate in an exchange. Let the cost of disconnecting an edge be the sum of the numbers of problems stored in the two AIs (at that moment). After the disconnection the two AIs lose their ability to exchange problems for future disconnections.\n\nThe task is to choose an order to disconnect all $n-1$ connections such that the total number of exchanged problems is minimized. Formally, if at the moment of disconnecting an edge, the two AIs involved hold $x$ and $y$ problems respectively, then the cost for that disconnection is $x+y$. Find the minimum possible total cost over all disconnection orders.\n\nIt can be shown that an optimal order exists which minimizes the sum of costs.\n\nNote: All formulas must be written in La(TeX) format. In particular, if an edge between components with sums (X) and (Y) is disconnected, the cost of that disconnection is (X+Y).

inputFormat

The first line contains a single integer (n) ((2\leq n\leq 2\cdot10^5)), the number of AIs.\n\nThe second line contains (n) integers (d_1,d_2,\dots,d_n) ((1\le d_i\le 10^9)) representing the initial number of problems in each AI.\n\nThe third line contains (n-1) integers (c_2,c_3,\dots,c_n), where for each (2\le i\le n), (c_i) ((1\le c_i < i)) indicates that AI (i) can communicate with AI (c_i). It is guaranteed that the same value of (c_i) appears at most twice.

outputFormat

Output a single integer, the minimum total number of exchanged problems if one disconnects all connections in an optimal order.

sample

3
1 1 1
1 1

5