Minimum Cost to Delete All Tree Edges

Given a tree with n nodes. Each node i has a weight \(w_i\). When you remove an edge, the tree splits into two connected components. The cost of removing that edge is equal to the sum of the maximum node weight in each of the two resulting subtrees. You can remove the edges in any order. Compute the minimum total cost required to remove all edges.

In other words, for each edge deletion, if the two resulting subtrees have maximum weights \(M_1\) and \(M_2\) respectively, the cost is \(M_1 + M_2\). It can be shown that the minimum total cost is given by:

\[ \text{Total Cost} = \begin{cases} 0, & \text{if } n=1, \\ \sum_{i=1}^{n} w_i + (n-2)\cdot\max_{1 \le i \le n}w_i, & \text{if } n \ge 2. \end{cases} \]

Your task is to implement a program that reads the tree description and outputs the minimum total cost.

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)) representing the number of nodes in the tree.

The second line contains \(n\) space-separated integers \(w_1, w_2, \dots, w_n\) where \(w_i\) is the weight of the \(i\)-th node (\(1 \le w_i \le 10^9\)).

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

outputFormat

Output a single integer: the minimum total cost to delete all edges in the tree.

sample

2
1 2
1 2

3

</p>