3940. Sjekira

【题目描述】

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

【输入格式】

第一行一个整数 $n$。

第二行 $n$ 个整数 $t_1,t_2,...,t_n$ 表示每个节点的权值。

接下来 $n-1$ 行每行两个整数 $x,y$ 表示 $x$ 和 $y$ 之间有一条边。

【输出格式】

输出一个数表示最小花费。

【样例输入1】

3
1 2 3
1 2
2 3

【样例输出1】

8

【样例输入2】

4
2 2 3 2
1 3
3 2
4 3

【样例输出2】

15

【样例输入3】

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

【样例输出3】

26

【数据规模与约定】

对于前 $20\%$ 的数据，保证 $1\le n\le 10$。

对于前 $50\%$ 的数据，保证 $1\le n\le 10^3$。

对于 $100\%$ 的数据，保证 $1\le n\le 10^5,1\le t_i\le 10^9$。