edgeremove

Edge Remove

There is a undirected connected graph with \(N\) nodes labelled from \(1\) to \(N\). Each node \(i \geq 2\) has an edge that connects \(i\) to \(c_i\). Note that \(c_i < i\) and the same value of \(c_i\) can appear no more than twice. Each node \(i\) also has a weight \(d_i\).

You wish to remove all edges in the graph, however there is a cost incurred when removing a edge which is the sum of the weights of the nodes of the removed edge when the edge is removed. You can remove the edges in any order, however immediately after removing an edge the weights of the two ndoes that was connected to the edge are swapped.

Find the minimum cost needed to remove all the edges.

Limits

\(1 \leq N \leq 5000\)
\(1 \leq d_i \leq 10^9\)

Subtasks #	Score	Constraits
1	10	\(N \leq 10\)
2	20	\(N \leq 100\)
3	13	\(N \leq 500\)
4	24	\(N \leq 1000\)
5	33	-

Input format

The first line contains \(N\).

The next line contains \(N\) integers, where the \(i^{th}\) integer represents \(d_i\)

The next line contains \(N-1\) integers, where the \(i^{th}\) integer represents \(c_{i+1}\)

Output format

Output the minimum cost

Samples

Sample Input 1	Sample Output 1
3 2 1 3 1 1	7

An optimal solution is to disconnect nodes \(1\) and \(2\) for a cost of \(2 + 1 = 3\) and the weights are swapped so now node \(1\) has a weight of \(1\). Then disconnect nodes \(1\) and \(3\) for a cost of \(1 + 3 = 4\). Thus the total cost is \(7\).