Tree Pruning Optimization

You are given a rooted tree with ( n ) nodes, where the root is node (1). In addition, you are given a cost function ( f_i ) defined for ( i=1,2,\dots,n ) (provided as an array of ( n ) integers). You may perform the following operation any number of times (possibly zero):

• Choose any node \(u\) and delete all nodes in the subtree of \(u\) except for \(u\) itself.

The cost of performing the operation at node (u) is ( f_{s_u} ), where ( s_u ) is the size (number of nodes) in the current subtree of ( u ) (including (u) itself). Note that when you delete nodes via an operation at (u), the node (u) remains and may later be deleted by a deletion in one of its ancestors. (The root (1), however, must remain in the final tree.)

Your goal is to delete all nodes except for node (1) while minimizing the total cost.

Understanding the Process

One valid strategy is to perform the deletion operation at the root \(1\) directly; the cost will then be \( f_{n} \) (since the whole tree has \( n \) nodes). However, it might be beneficial to perform some deletion operations deeper in the tree to reduce the size of some subtrees (and thus lower the cost of a subsequent deletion higher up).

Formal Specification

Let \( T(u) \) denote the total number of nodes in the subtree of node \( u \) (in the original tree), and define an option for any nonleaf node \( u \) to "prune" its children so that it becomes effectively a leaf (i.e. its remaining subtree size becomes \(1\)). For any non-root node \( u \), its removal must be carried out by an operation on its parent. In other words, if \( u \) is not pruned internally then it will contribute \( T(u) \) to the size of its parent’s subtree when that parent eventually gets deleted. Alternatively, if you perform a sequence of pruning operations in the subtree of \( u \) so that \( u \) becomes a leaf, then \( u \) will contribute \( 1 \) to its parent’s count at an extra cost.

With this observation, one may show that the final answer is given by \[ \min\Bigl(f_{T(1)},\; f_1 + \sum_{v \in children(1)} F(v)\Bigr), \] where for any non-root node \( u \) (with \( T(u) > 1 \)) the value \( F(u) \) is defined by \[ F(u) = \min\Bigl( f_{T(u)},\; f_1 + \sum_{v \in children(u)} F(v)\Bigr), \] and for a leaf \( u \) we set \( F(u)=0 \).

In other words, you have two ways to remove the nodes in a subtree:

1. Delete the entire subtree in one go by applying the operation at that node (cost \( f_{T(u)} \)).
2. Recursively prune all children so that the node becomes a leaf and then have its parent remove it later (this costs \( f_1 \) for the deletion at the parent plus the extra cost to prune each child).

Compute and output the minimum total cost needed to delete all nodes except for the root \(1\).

inputFormat

The first line contains an integer \( n \) (\( 1 \le n \le 10^5 \)) representing the number of nodes in the tree.

The second line contains \( n-1 \) integers. For \( i=2,3,\dots,n \), the \( (i-1)\)th integer is the parent of node \( i \) (it is guaranteed that the tree is rooted at node 1).

The third line contains \( n \) integers: \( f_1, f_2, \dots, f_n \), where \( f_i \) is the cost for performing a deletion operation when the current subtree has exactly \( i \) nodes.

outputFormat

Output a single integer — the minimum total cost to delete all nodes except for node 1.

sample

3
1 2
5 10 20

10