P7162 [COCI 2020/2021 #2] Sjekira

有一棵 $n$ 个结点的树，每个结点有一个权值，删除一条边的费用为该边连接子树中结点权值最大值之和。问以任意顺序删除树中所有边的最小花费。

第一行一个整数 $n$，表示结点数。 第二行 $n$ 个整数 $t_1, t_2, \ldots , t_n$，其中第 $i$ 个数表示结点 $i$ 的权值。 接下来 $n-1$ 行，每行两个整数 $x, y$，表示 $x$ 和 $y$ 之间有一条边。

输出一个数，代表最小花费。

**【样例解释 #1】** 先删 $(2,3)$，再删 $(1,2)$，花费为 $5+3=8$。 **【数据范围】** 对于 $100\%$ 的数据，$1 \leq n \leq 100,000$，$1 \leq t_i \leq 10^9$。 Subtask #1（$10$ pts）：$n \leq 10$。 Subtask #2（$10$ pts）：$i$ 与 $i-1$ 有边直接相连。 Subtask #3（$30$ pts）：$n \leq 1000$。 Subtask #4（$50$ pts）：无附加限制。 **【说明】** 译自 [Croatian Open Competition in Informatics 2020 ~ 2021 Round 2 D Sjekira](https://hsin.hr/coci/contest2_tasks.pdf)。