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.
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.
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$$$.
41 2 3 41 22 32 4
8
510 1 1 1 11 22 33 44 5
10
