一棵无根树，节点编号 $1,2,\cdots,n$ ，节点 \(i\) 的硬度为 \(h_i\) 。

现在要按一定的顺序砍掉这棵树的 \(n-1\) 条边，最终这棵树将变成 \(n\) 个独立的节点。

砍树很费力气，将一个连通块砍成两个连通块时消耗的力气等于这两个连通块的最大硬度之和。

砍掉整棵树消耗的力气总和最小是多少呢？

第一行一个整数 \(n\) 。

第二行 \(n\) 个整数 \(h_1,h_2,\cdots,h_n\) 。

接下来 \(n-1\) 行，每行两个整数 \(u,v\) 表示一条边。

输出一个整数答案。

样例1解释

一种方案是先砍 \((1,2)\) 边花费 $1+3=4$ 力气，再砍 \((2,3)\) 边花费 $2+3=5$ 力气，总共花费 $9$ 力气。 另一种方案是先砍 \((2,3)\) 边花费 $2+3=5$ 力气，再砍 \((1,2)\) 边，花费 $1+2=3$ 力气，总共花费 $8$ 力气。

数据范围

对于所有数据， \(1\leq n\leq 10^5\) ， \(1\leq t_i\leq 10^9\) 。

子任务采用捆绑测试。

• 子任务1（ $10$ 分）： \(n\leq 10\) ；
• 子任务2（ $10$ 分）： 每条边满足 \(|u-v|=1\) ；
• 子任务3（ $25$ 分）： \(n\leq 10^3\) ；
• 子任务4（ $55$ 分）：无附加条件。