P5533 [CCO 2019] Winter Driving

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.

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$.

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

### 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