P7162 [COCI 2020/2021 #2] Sjekira

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.

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 one number, the minimum total cost.

**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](https://hsin.hr/coci/contest2_tasks.pdf)。 Translated by ChatGPT 5