In Premiernation, there are $N$ cities, with $a_i$ people in the $i$-th city. $N-1$ roads currently connect the cities. These roads are structured in such a way that if they were all bidirectional, there would exist a single unique path connecting any pair of cities. Sadly, these roads are unidirectional. Adding onto the sadness, the main form of communication in Premiernation comes in the form of trucking around piles of SSDs. A communication connection can exist between two distinct people $A$ and $B$ if it is possible to travel from the city $A$ lives in to the city $B$ lives in using only the roads that exist in Premiernation. You have been given the roadrollifier, a tool which can convert a unidirectional road to a bidirectional road. However, since the roadrollifier is a one-time-use item (and thus can only convert one road), the Premier wishes to maximize the social benefits of using it.

As such, the Premier has tasked you with calculating the maximum number of connections that will exist after using the roadrollifier once.

Constraints

For all subtasks:

$1\le N\le 2\times {10}^5$

$1\le a_i\le 1\times {10}^5$

$1\le u_j,v_j\le N$

Subtask 1 [20%]

$1\le N\le 1000$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain $N$, the number of cities in Premiernation.

The next line will contain $N$ space-separated integers $a_1,a_2,\dots ,a_N$.

The next $N-1$ lines will each contain two space-separated integers $u_j$ and $v_j$, denoting that city $u_j$ has a one-way road directed towards city $v_j$.

Output Specification

Output a single number, the maximum number of connections that can exist after one use of the roadrollifier.

Sample Input 1

4
4 2 3 4
1 2
2 3
3 4

Sample Output 1

106

Explanation of Sample Output 1

Initially, there exist $94$ connections:

• Each city $1$ resident has $3$ connections with other city $1$ residents, $2$ connections with city $2$ residents, $3$ connections with city $3$ residents, and $4$ connection with city $4$ residents. Since there are $4$ city $1$ residents, $4\times (3+2+3+4)=48$.
• Each city $2$ resident has $1$ connection with other city $2$ residents, $3$ connections with city $3$ residents, and $4$ connections with city $4$ residents. Since there are $2$ city $2$ residents, $2\times (1+3+4)=16$.
• Each city $3$ resident has $2$ connections with other city $3$ residents and $4$ connections with city $4$ residents. Since there are $3$ city $3$ residents, $3\times (2+4)=18$.
• Each city $4$ resident has $3$ connections with other city $4$ residents. Since there are $4$ city $4$ residents, $4\times 3=12$.

In all, $48+16+18+12=94$.

It can be shown that using the roadrollifier on the edge connecting city $3$ to city $4$ results in the greatest number of connection increases - resulting in an extra $12$ connections for $106$ total connections.

Sample Input 2

9
1 2 3 4 5 6 7 8 9
1 2
2 4
2 5
3 2
6 3
5 8
9 5
5 7

Sample Output 2

974

Explanation of Sample Output 2

Without using the roadrollifier, the number of connections that would exist would be $821$. It can be shown that the roadrollifier should be used on the road connecting city $9$ to city $5$, resulting in an increase of $153$ connections. $821+153=974$, so $974$ is the answer to this case.