Description

There is a tree with $n$ nodes, and each node has a weight. The cost of deleting an edge is the sum of the maximum node weight in each of the two subtrees formed by that edge. Find the minimum total cost to delete all edges of the tree in any order.

Input Format

The first line contains an integer $n$, the number of nodes.
The second line contains $n$ integers $t_1, t_2, \ldots , t_n$, where the $i$-th number is the weight of node $i$.
The next $n-1$ lines each contain two integers $x, y$, meaning there is an edge between $x$ and $y$.

Output Format

Output one number, the minimum total cost.

3
1 2 3
1 2
2 3

8

4
2 2 3 2
1 3
3 2
4 3

15

5
5 2 3 1 4
2 1
3 1
2 4
2 5

26

Hint

Sample Explanation #1

Delete $(2,3)$ first, then delete $(1,2)$. The cost is $5+3=8$.

Constraints

For $100\%$ of the testdata, $1 \leq n \leq 100,000$ and $1 \leq t_i \leq 10^9$.

Subtask #1 ($10$ pts): $n \leq 10$.
Subtask #2 ($10$ pts): There is an edge directly connecting $i$ and $i-1$.
Subtask #3 ($30$ pts): $n \leq 1000$.
Subtask #4 ($50$ pts): No additional constraints.

Notes

Translated from Croatian Open Competition in Informatics 2020 ~ 2021 Round 2 D Sjekira。

Translated by ChatGPT 5