题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3
1 2 3
1 2
2 3

样例输出 #1

8

样例 #2

样例输入 #2

4
2 2 3 2
1 3
3 2
4 3

样例输出 #2

15

样例 #3

样例输入 #3

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

样例输出 #3

26

提示

【样例解释 #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）：无附加限制。