Problem Background

"It rains heavily on Qingming Festival, and travelers on the road are almost soul-broken."

Qingming Festival of the year 2075 saw no spring rain. Under the blanket of flying snow, only the snow vehicles carrying the faint hope of humanity were traveling through the icy plains.

The journey of 4.22 light-years away seems to be incredibly lonely for Earth, this solitary traveler.

Problem Description

Only a hundred kilometers away from Sulawesi, the air inside the vehicle was even colder than outside. Four pairs of eyes were fixed on the screen in front of Ailifen, which was the key program controlling the planetary engines: Spring Festival Twelve Chimes. She needed to deploy it to a chip in the power control system.

"Spring Festival Twelve Chimes" consists of \( n \) subprograms, where the \( i \)-th subprogram requires \( M_i \) memory space. The calling relationship between these \( n \) subprograms forms a tree with the first subprogram as the root, where the parent of the \( i \)-th subprogram in the calling tree is the \( f_i \)-th subprogram.

Due to memory constraints, the power control chip provides a memory segmentation mechanism. You can divide the memory into several segments \( S_1, S_2, \ldots, S_k \), and pre-assign each program to a fixed segment. Two subprograms can be assigned to the same segment if and only if they do not have a direct or indirect calling relationship. In other words, subprograms \( a \) and \( b \) can be assigned to the same segment if and only if \( a \) and \( b \) are not in an ancestor-descendant relationship in the calling tree.

The size of a segment should be the maximum of the memory requirements of all subprograms assigned to that segment, and the sum of the sizes of all segments cannot exceed the system's memory size.

Now Ailifen wants to know the minimum memory required for the power control chip to ensure the correct operation of the Spring Festival Twelve Chimes. That is, the minimum memory needed to divide the memory into several segments and assign each subprogram to a segment such that no subprograms in the same segment have an ancestor-descendant relationship.

Input Format

The first line contains a positive integer \( n \), representing the number of subprograms, where \( n \leq 2 \times 10^5 \).

The second line contains \( n \) positive integers \( M_1, M_2, \ldots, M_n \), separated by spaces, where \( M_i \) represents the memory space required by the \( i \)-th subprogram.

The third line contains \( n - 1 \) positive integers \( f_2, f_3, \ldots, f_n \), separated by spaces, where \( f_i < i \) represents that the parent of the \( i \)-th subprogram in the calling tree is the \( f_i \)-th subprogram.

Output Format

A single integer representing the minimum memory requirement.

Sample Input and Output

Input Sample #1

5
10 20 20 30 30
1 1 2 2

Output Sample #1

60

Input Sample #2

10
2 1 1 1 1 2 1 1 1 2
1 1 1 4 5 3 3 4 3

Output Sample #2

6

Input Sample #3

15
10 1 10 10 2 6 9 6 8 6 3 4 4 5 5
1 2 2 1 5 4 4 1 2 10 1 9 6 1

Output Sample #3

31

Notes

Sample 1 Explanation

In the optimal solution, the memory is divided into three segments of sizes 10, 20, and 30. The first subprogram is assigned to the first segment, the second and third subprograms are assigned to the second segment, and the fourth and fifth subprograms are assigned to the third segment. It can be proven that no better solution exists.

Subtasks

Note: In test cases 10, 11, and 12, the first subprogram is not necessarily an endpoint of the chain.

Where \( M \) is the maximum of all subprogram memory requirements, i.e., \( \max\{M_i\} \).

For all data, \( 1 \leq n \leq 2 \times 10^5 \), \( 1 \leq M \leq 10^9 \).

After carefully reading the problem statement and analyzing the data range, Ailifen began to write the program to solve this problem.

$ login Elephant
password: ********

Ailifen, senior programmer. Yuyang City Third Engineering Team reminds you:

• Read the problem carefully;
• Code with proper standards, or you'll get zero points.

$ cd spring
$ ac spring
Spring Accepted. Score: 100/100.

见题面 Input 部分

见题面 Output 部分