Canadian Computing Olympiad: 2019 Day 1, Problem 3

In the Great White North, there are $N$ cities numbered from $1$ to $N$. There are $A_i$ citizens living in city $i$. There are $N-1$ roads numbered from $2$ to $N$. Road $j$ connects city $j$ and city $P_j$, where $P_j<j$. There are at most $36$ roads connected to any city.

During winter, all roads will be converted into one-way highways due to dangerous driving conditions. That is, road $j$ will become a highway that is either one-way from city $j$ to city $P_j$ or one-way from city $P_j$ to city $j$.

Every citizen wants to send a holiday card to every other citizen. Citizen $x$ can send a card to citizen $y$ if it is possible to travel from the city $x$ lives in to the city $y$ lives in using only highways.

What is the maximum number of holiday cards that can be sent after converting all roads to highways?

Input Specification

The first line contains one integer $N$ $(2\le N\le 200000)$.

The second line contains $N$ integers $A_1,\dots ,A_N$ $(1\le A_i\le 10000)$.

The third line contains $N-1$ integers $P_2,\dots ,P_N$ $(1\le P_j\le j)$.

Let $D$ be the maximum number of roads connected to any city. It is guaranteed that $D\le 36$.

For 5 of the 25 available marks, $N\le 10$.

For an additional 5 of 25 available marks, $N\le 1000$ and $D\le 10$.

For an additional 5 of 25 available marks, $D\le 18$.

For an additional 5 of 25 available marks, there will be 37 cities, where one city is connected to 36 other cities, and these other 36 cities are only connected to this one city.

Output Specification

Print one line with one integer, the maximum number of cards that can be sent after converting all roads to highways.

Sample Input

4
3 3 4 1
1 2 1

Output for Sample Input

67

Explanation of Output for Sample Input

One possible way of converting roads to highways is for road 2 to become one-way from city 2 to city 1, road 3 to become one-way from city 3 to city 2, and road 4 to become one-way from city 1 to city 4.

Consider the following pictures, with the cities and associated population (in parentheses) for the initial roads

and what it looks like after all roads are converted to highways:

Every citizen in city 3 can send 3 holiday cards to city 3 citizens, 3 holiday cards to city 2 citizens, 3 holiday cards to city 1 citizens, and 1 holiday card to the city 4 citizen, for a total of 40 holiday cards sent out of city 3.

Similarly,

• city 2 citizens send 6 holidays cards each, for a total of 18 holiday cards.
• city 1 citizens send 3 holidays cards each, for a total of 9 holiday cards.
• the city 4 citizen cannot send any holiday cards.

A total of $40+18+9=67$ holiday cards are sent.