Problem Description

There is a tree with $n$ nodes, each having a weight. The cost of deleting an edge is the sum of the maximum weights of the nodes in the subtrees connected by that edge. Determine the minimum total cost to delete all edges in the tree in any order.

Input Format

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

Output Format

Output a single number representing the minimum cost.

Sample Input and Output

Sample Input #1

3
1 2 3
1 2
2 3

Sample Output #1

8

Sample Input #2

4
2 2 3 2
1 3
3 2
4 3

Sample Output #2

15

Sample Input #3

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

Sample Output #3

26

Notes/Hints

[Sample Explanation #1]

First delete edge $(2,3)$, then delete edge $(1,2)$, with a cost of $5+3=8$.

[Data Range]

For $100\%$ of the data, $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 node $i$ with node $i-1$.
Subtask #3 ($30$ pts): $n \leq 1000$.
Subtask #4 ($50$ pts): No additional constraints.

[Note]

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

见题面 Input 部分

见题面 Output 部分