Maximum Delivered Holiday Cards

In the Snow White Empire there are N cities numbered from \(1\) to \(N\). City \(i\) has \(A_i\) residents. There are \(N-1\) roads; for every road \(j\) \( (2\le j\le N)\), it connects city \(j\) and city \(P_j\) (with \(P_j < j\)). It is guaranteed that each city is incident to at most 36 roads.

In winter, due to dangerous driving conditions, the government converts every road into a one‐way highway. For each road \(j\), you may choose its orientation: either from city \(j\) to city \(P_j\) or from city \(P_j\) to city \(j\).

After the conversion, every resident wishes to send a holiday greeting card to every other citizen. A card sent from a resident in city \(X\) to a resident in city \(Y\) will be successfully delivered if and only if either \(X=Y\) or there is a directed path from \(X\) to \(Y\) along the highways.

Your task is to choose an orientation for each road in order to maximize the total number of delivered greeting cards (note that for every two different cities, at most one direction of delivery can be achieved because a directed cycle over distinct vertices is impossible in a tree).

Observation: For any pair of distinct cities, you can at most guarantee delivery in one direction. In an optimal configuration the total number of delivered cards is \(\frac{(\sum_{i=1}^N A_i)^2 - \sum_{i=1}^N A_i^2}{2}\). However, note that it may not always be possible to achieve this ideal for every pair due to the tree structure. You need to determine, by choosing each road’s orientation appropriately, what is the maximum possible total number of delivered cards (each card counts \(A_u \times A_v\) for a successful delivery from a resident in city \(u\) to a resident in city \(v\)).

Input Constraints:

• \(2 \le N \le 20\) (The limit on \(N\) is small so that a brute force solution over \(2^{N-1}\) possibilities is feasible.)
• \(1 \le A_i \le 10^9\)
• For every \(j\) with \(2\le j\le N\), \(1 \le P_j < j\).
• Each city is incident to at most 36 roads.

inputFormat

The first line contains a single integer \(N\), the number of cities.

The second line contains \(N\) space‐separated integers \(A_1, A_2, \dots, A_N\) representing the populations of the cities.

The third line contains \(N-1\) space‐separated integers \(P_2, P_3, \dots, P_N\) where for each \(2 \le j \le N\), city \(j\) is connected to city \(P_j\) (with \(P_j < j\)).

outputFormat

Output a single integer, the maximum possible total number of delivered greeting cards.

(Note: For any pair of distinct cities \(u,v\), if the delivery from one side is successful, it contributes \(A_u \times A_v\) to the total count.)

sample

3
1 2 3
1 2

11