B. Balanced Codex of Knuth
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Deep within the Stanford archives, Donald Knuth has unveiled a lost volume of The Art of Computer Programming — but its chapters are scattered across an ancient, unrooted tree of cross-references. Each chapter carries a scholarly weight $$$w_i$$$, representing how much intellectual effort a reader must invest to digest it.

Knuth, ever the perfectionist, insists that the codex must be read starting from a single root chapter. Once a root is chosen, every other chapter sits at some depth $$$d_i$$$ — the number of edges on the unique path from the root to chapter $$$i$$$ (the root itself has depth $$$0$$$). The total reading cost of the codex is then defined as:

$$$$$$\mathrm{cost}(r) = \sum_{i=1}^{n} d_i(r) \cdot w_i,$$$$$$

where $$$d_i(r)$$$ is the depth of chapter $$$i$$$ when chapter $$$r$$$ is chosen as the root.

Because Knuth would never tolerate a suboptimal edition, your task is to determine the minimum possible total reading cost over all valid choices of root $$$r \in {1, 2, \dots, n}$$$.

You are given the tree with $$$n$$$ chapters (nodes) and $$$n-1$$$ cross-references (edges), together with the weight $$$w_i$$$ of each chapter. The tree is unrooted: any chapter may serve as the root.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^6$$$), the number of chapters in Knuth's codex.

The second line contains $$$n$$$ integers $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 10^3$$$), the scholarly weights of the chapters.

Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), denoting a cross-reference (an undirected edge) between chapters $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

Output

Print a single integer: the minimum possible value of $$$\sum_{i=1}^{n} d_i(r) \cdot w_i$$$ over all choices of root $$$r$$$.

Examples
Input
4
1 2 3 4
1 2
2 3
2 4
Output
8
Input
5
10 1 1 1 1
1 2
2 3
3 4
4 5
Output
10