시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.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.

예제 입력 1

4
3 3 4 1
1 2 1

예제 출력 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,

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