Description

There are $N$ cities in the Northern White Empire, numbered from $1$ to $N$. In city $i$, there are $A_i$ residents.

There are $N - 1$ roads, numbered from $2$ to $N$. Road $j$ connects city $j$ and city $P_j$, where $P_j \lt j$. Each city is connected to at most 36 roads.

In winter, dangerous driving conditions cause the government to enforce traffic control, and all roads become one-way highways. That is, for each road $j$, it becomes either a one-way highway from city $j$ to city $P_j$, or a one-way highway from city $P_j$ to city $j$.

Now, every resident wants to send holiday cards to all other citizens. However, to send a holiday card from city $X$ to city $Y$, it must be possible to travel from $X$ to $Y$ using the highways, or $X = Y$.

Find the maximum total number of cards that can be delivered after all roads are converted into one-way highways.

Input Format

The first line contains a positive integer $N$.

The second line contains $N$ positive integers $A_1$ to $A_N$.

The third line contains $N - 1$ positive integers $P_2$ to $P_N$.

Output Format

One line containing a positive integer, the maximum total number of holiday cards that can be delivered.

4
3 3 4 1
1 2 1

67

Hint

Sample Explanation

One possible way is to convert:

into:

Then, each resident in city 3 can send 3 cards to city 3, 3 cards to city 2, 3 cards to city 1, and 1 card to city 4. So city 3 can send a total of 40 cards.

Similarly, city 2 can send 18 cards in total, city 1 can send 9 cards in total, and city 4 cannot send any cards.

So the answer is $40 + 18 + 9 + 0 = 67$.

Constraints

$2 \le N \le 200\,000$

For any valid $i$, $1 \le A_i \le 10\,000$

For any valid $j$, $1 \le P_j \le j$

Let $D$ be the number of roads connected to any city. $D \le 36$.

Subtasks

Subtask 1 (20 points): $N \le 10$

Subtask 2 (20 points): $N \le 1000$, $D \le 10$

Subtask 3 (20 points): $D \le 18$

Subtask 4 (20 points): $N = 37$, and all roads connect to one city, i.e. this city has 36 connected cities, and each of those cities is connected to it by only one road.

Subtask 5 (20 points): No additional constraints.

Translated by ChatGPT 5