| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 6 | 5 | 5 | 100.000% |
In the Great White North, there are N cities numbered from 1 to N. There are Ai citizens living in city i. There are N − 1 roads numbered from 2 to N. Road j connects city j and city Pj, where Pj < 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 Pj or one-way from city Pj 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?
The first line contains one integer N (2 ≤ N ≤ 200 000).
The second line contains N integers A1, · · · , AN (1 ≤ Ai ≤ 10 000).
The third line contains N − 1 integers P2, · · · , PN (1 ≤ Pj ≤ j).
Let D be the maximum number of roads connected to any city. It is guaranteed that D ≤ 36.
Print one line with one integer, the maximum number of cards that can be sent after converting all roads to highways.
4 3 3 4 1 1 2 1
67
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,
A total of 40 + 18 + 9 = 67 holiday cards are sent.