题目描述

给定一棵有 $n$ 个点构成的树，点的编号依次为 $1$ 到 $n$，每个点都有点权 $a_i$，你需要删除所有 $n - 1$ 条边。

其中，每删除一条边的代价为：与这条边相连的两个连通块中，各自的最小点权之和。换句话说，设两个连通块中的最小点权分别为 $x$ 与 $y$，则本次代价为 $x+y$。

你需要求解最小总代价。

【名词解释】 连通块：对于树上的任意一个点集 $\Bbb S$，如果点集中的任意两点 $u,v$ 满足“ $u$ 到 $v$ 的简单路径上的所有点都在 $\Bbb S$ 中”，则称 $\Bbb S$ 是一个连通块。特别地，单独的点也构成一个连通块。

输入格式

第一行输入一个整数 $n$，表示树上点的数量。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每个点的点权。

此后 $n - 1$ 行，第 $i$ 行输入两个整数 $u_i,v_i$，表示第 $i$ 条边连接 $u_i$​ 和 $v_i$​。保证数据给出的是一棵合法的树。

输出格式

输出一个整数，表示最小代价。

4
1 2 3 4
1 2
2 3
3 4

12

5
1 3 2 7 6
1 4
4 2
3 4
5 4

22

样例解释

在第一组样例中，最优的删除方案为：

$∙$ 删除 $3 {\texttt{-}} 4$ 的边，代价为 $1+4=5$；

$∙$ 删除 $2 {\texttt{-}} 3$ 的边，代价为 $1+3=4$；

$∙$ 删除 $1 {\texttt{-}} 2$ 的边，代价为 $1+2=3$。

$∙$ 总代价为 $5+4+3=12$。

数据规模与约定

下发文件

下发文件对应子任务 $3,4,5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $2 \leq n \leq 10^6,1 \leq a_i \leq 10^9,1 \leq u_i,v_i \leq n$。保证输入构成一棵树。