小䓤的树

题号：NC222915
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一棵树，点有点权，要求你重新构建这棵树，使得这棵树在代价最小的情况下满足除了权值最小的点外，每个点都有一个权值比它小的点与它相邻。计算代价的方法如下：

一个点的代价为 $\text{deg}_u \times a_u$
，其中 $\text{deg}_u$ 表示点 u 的度数，即与 u 直接相连的节点数。
一条边 (u,v)的代价为 $\text{dis}(u,v) \times \min(a_u,a_v)$ ，其中 $\text{dis}(u,v)$ 为 u 和 v 在原树中的距离。
一棵树的代价为点的代价 + 边的代价。

输入描述:

第一行一个数 n ，表示 n 个点的树。

第二行 n 个数表示每个点的点权。

接下来 n-1 行每行两个整数x，y表示树上有一条连接x，y的边

输出描述:

一行一个数表示最小代价

示例1

输入

复制

输出

复制

说明

一种最优策略为：
连边 ，其点的代价为 边的代价为 ，总代价为  ，可以发现没有更优的策略。

示例2

输入

复制

输出

复制

题目描述

输入描述:

输出描述:

输入

输出

说明

输入

输出

备注: