Optimal Hospital Placement on a Binary Tree

You are given a binary tree with n nodes. Each node i has a population p_i. The tree is provided as an undirected graph with n-1 edges, and the distance between any two adjacent nodes is 1. Your task is to choose a node on which to build a hospital so that the sum of the distances traveled by all residents is minimized. When the hospital is built on a node, the residents of that node do not have to travel.

More formally, if you build the hospital at node u, the total travel distance is given by:

[ D(u)=\sum_{v=1}^{n} p_v \cdot d(u,v) ]

where \(d(u,v)\) is the number of edges in the unique path between nodes \(u\) and \(v\). You need to output the minimum possible value of \(D(u)\) among all nodes \(u\).

Example: Consider the following tree:

• Node 1: population = 13
• Node 2: population = 4
• Node 3: population = 12
• Node 4: population = 20
• Node 5: population = 40

The edges of the tree are:

• 1 - 2
• 1 - 3
• 3 - 4
• 3 - 5

If the hospital is built at node 1, the sum of distances is:

[ D(1)= 1\times4+ 1\times12+ 2\times20+ 2\times40 = 136 ]

If the hospital is built at node 3, then:

[ D(3)= 1\times13+ 2\times4+ 1\times20+ 1\times40 = 81 ]

Thus, the optimal answer is 81.

inputFormat

The first line contains an integer n (2 ≤ n ≤ 10⁵) indicating the number of nodes in the tree.

The second line contains n space-separated integers p₁, p₂, ..., p_n (each between 1 and 10⁴), where p_i is the population at node i.

Each of the next n-1 lines contains two integers u and v (1 ≤ u,v ≤ n) representing an edge between nodes u and v.

outputFormat

Output a single integer: the minimum possible sum of traveling distances multiplied by the respective populations when the hospital is optimally placed.

sample

5
13 4 12 20 40
1 2
1 3
3 4
3 5

81