H. Wings of Crystals
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Everyone is aware that Flandre has wings adorned with crystals. However, it is less commonly known that her wings are actually made by herself.

Flandre has been given a tree composed of $$$n$$$ crystals interconnected by $$$n-1$$$ edges. This arrangement ensures that each crystal is directly or indirectly connected to others. The beauty value of the $$$i$$$-th crystal is denoted as $$$a_i$$$.

A "wing" is defined as a sequence of arbitrary length with non-repeating elements $$$b_1, b_2, \ldots, b_k$$$ ($$$1 \le b_i \le n$$$) such that for every integer $$$1 \leq i \lt k$$$, the $$$b_i$$$-th crystal and the $$$b_{i+1}$$$-th crystal is connected by a single edge within the tree. The beauty value of a wing is calculated as the square of the sum of the beauty values of all included crystals, expressed mathematically as $$$\left(\sum\limits_{i=1}^k a_{b_i}\right)^2$$$.

Flandre wants to craft some wings from the crystals in this tree, such that each crystal is contained by no more than one wing. Help her determine the maximum possible sum of the beauty values for the wings she can create.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \times 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 5000$$$).

Each of the following $$$n-1$$$ lines contains two integers $$$u, v$$$ ($$$1 \le u, v \le n$$$), denoting an edge connecting the $$$u$$$-th and the $$$v$$$-th crystal in the tree. It is guaranteed that the given edges form a tree.

Output

Output a single integer, the maximum possible sum of beauty values for the wings.

Examples
Input
1
19
Output
361
Input
3
100 100 500
1 2
1 3
Output
490000
Input
6
10 20 20 10 20 20
1 2
1 3
4 5
4 6
1 4
Output
5000
Input
9
0 1 0 1 1 0 1 1 1
1 2
1 3
1 4
1 5
2 6
2 7
3 8
6 9
Output
14
Note

In the first example, Flandre can craft a single wing of the only crystal with beauty value $$$19^2 = 361$$$.

In the second example, Flandre can craft a single wing consisting of all $$$n$$$ crystals with beauty value $$$(100 + 100 + 500)^2 = 490000$$$.

In the third example, Flandre can craft two wings $$$[2, 1, 3]$$$ and $$$[5, 4, 6]$$$. The sum of their beauty values is $$$(20 + 10 + 20)^2 + (20 + 10 + 20)^2 = 5000$$$.