New Year Twelve Chimes

In the control program called New Year Twelve Chimes, there are n subprograms. The i-th subprogram requires a memory size of (M_i). Their calling relationships form a rooted tree with node 1 as the root, where for (i \ge 2) the parent of node (i) is given by (f_i).

Because memory is scarce, the power‐control chip provides a segmented memory mechanism. You can divide memory into several segments (S_1, S_2, \dots, S_k) and pre-allocate each subprogram to one fixed segment. Two subprograms can be allocated to the same segment if and only if they are not in an ancestor–descendant relationship in the call tree (i.e. neither is an ancestor of the other).

For each segment, its size is determined by the maximum (M_i) among the subprograms allocated to it. The sum of the sizes of all segments must not exceed the chip’s total memory.

The problem asks: What is the minimum total memory required for the program to run correctly? In other words, what is the minimum memory size (T) for which it is possible to partition memory into segments and allocate each subprogram to one segment so that in each segment no two subprograms are in an ancestor–descendant relationship and the sum of the segment sizes (each being the maximum (M_i) in that segment) does not exceed (T)?

A key observation is that because any valid allocation requires that on every root–to–leaf path, all subprograms must go to distinct segments, one possible (and optimal) strategy is to allocate subprograms by their depth in the tree. Notice that all subprograms at the same depth are not in an ancestor–descendant relationship and can share the same segment. Therefore, if we let (D) be the maximum depth and define for each (d = 1, 2, \dots, D), [ C(d) = \max{M_i \mid \text{node } i \text{ is at depth } d}, ] then a valid allocation is to assign all nodes at depth (d) into one segment of size (C(d)). This yields a total memory requirement of [ T = \sum_{d=1}^{D} C(d). ]

Your task is to compute this minimum total memory required.

Input Format:

• The first line contains an integer \(n\) (the number of subprograms).
• The second line contains \(n\) space‐separated integers: \(M_1, M_2, \dots, M_n\).
• The third line contains \(n-1\) space‐separated integers: \(f_2, f_3, \dots, f_n\) where \(f_i\) is the parent of node \(i\) in the tree.

Output Format:

• Output a single integer, the minimum total memory required.

Constraints:

• You may assume that \(n\) is at least 1.
• The tree is rooted at node 1.
• It is guaranteed that the input forms a valid tree.

inputFormat

The input begins with an integer \(n\) (n ≥ 1), representing the number of subprograms.

The second line contains \(n\) space‐separated integers \(M_1, M_2, \dots, M_n\) where \(M_i\) is the memory required by the i-th subprogram.

The third line contains \(n-1\) space‐separated integers \(f_2, f_3, \dots, f_n\), where \(f_i\) is the parent of subprogram \(i\) in the call tree.

outputFormat

Output a single integer: the minimum total memory required.

Explanation: Compute the depth of each node (with the root having depth 1). For each depth \(d\), let \(C(d)\) be the maximum \(M_i\) among all nodes at that depth; the answer is \(\sum_{d} C(d)\).

sample

3
2 1 3
1 2

6