「LAOI-15」不知道起什么名字
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给定一棵有 n 个点构成的树，点的编号依次为 1 到 n，每个点都有点权 a_i，你需要删除所有 n-1 条边。
\hspace{15pt}其中，每删除一条边的代价为：与这条边相连的两个连通块中，各自的最小点权之和。换句话说，设两个连通块中的最小点权分别为 x 与 y，则本次代价为 x+y。
\hspace{15pt}你需要求解最小总代价。

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

输入描述:

\hspace{15pt}第一行输入一个整数 n\left(2\le n \le 10^6\right)，表示树上点的数量。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(1\le a_i\le10^9\right)，表示每个点的点权。
\hspace{15pt}此后 n-1 行，第 i 行输入两个整数 u_i,v_i\left(1\le u_i,v_i \le n\right)，表示第 i 条边连接 u_i 和 v_i。保证数据给出的是一棵合法的树。

输出描述:

\hspace{15pt}输出一个整数，表示最小代价。
示例1

输入

复制 
4
1 2 3 4
1 2
2 3
3 4

输出

复制 
12

说明

\hspace{15pt}在这个样例中，最优的删除方案为：
\hspace{23pt}\bullet\,删除 3 {\texttt{-}} 4 的边，代价为 1+4=5；
\hspace{23pt}\bullet\,删除 2 {\texttt{-}} 3 的边，代价为 1+3=4；
\hspace{23pt}\bullet\,删除 1 {\texttt{-}} 2 的边，代价为 1+2=3。
\hspace{23pt}\bullet\,总代价为 5+4+3=12。
示例2

输入

复制 
5
1 3 2 7 6
1 4
4 2
3 4
5 4

输出

复制 
22

备注: