Ehab and a weird weight formula

题意翻译

给定一棵树，点有点权，其中这棵树满足除了权值最小的点外，每个点都有一个权值比它小的点与它相邻。 要求你重新构建这棵树，使得代价最小。计算代价的方法如下： 现在规定： - 一个点的代价为：$\text{deg}_u \times a_u$，其中 $\text{deg}_u$ 表示点 $u$ 的度数，即与 $u$ 直接相连的节点数。 - 一条边 $(u,v)$ 的代价为 $\lceil \log_2 \text{dis}(u,v) \rceil \times \min(a_u,a_v)$，其中 $\text{dis}(u,v)$ 为 $u$ 和 $v$ 在原树中的距离。 一棵树的代价为点的代价 + 边的代价。 保证原树中权值最小的点唯一。

题目描述

You're given a tree consisting of $ n $ nodes. Every node $ u $ has a weight $ a_u $ . It is guaranteed that there is only one node with minimum weight in the tree. For every node $ u $ (except for the node with the minimum weight), it must have a neighbor $ v $ such that $ a_v<a_u $ . You should construct a tree to minimize the weight $ w $ calculated as follows: - For every node $ u $ , $ deg_u \cdot a_u $ is added to $ w $ ( $ deg_u $ is the number of edges containing node $ u $ ). - For every edge $ \{ u,v \} $ , $ \lceil log_2(dist(u,v)) \rceil \cdot min(a_u,a_v) $ is added to $ w $ , where $ dist(u,v) $ is the number of edges in the path from $ u $ to $ v $ in the given tree.

输入输出格式

输入格式

The first line contains the integer $ n $ $ (2 \le n \le 5 \cdot 10^5) $ , the number of nodes in the tree. The second line contains $ n $ space-separated integers $ a_1, a_2, \ldots, a_n $ $ (1 \le a_i \le 10^9) $ , the weights of the nodes. The next $ n-1 $ lines, each contains 2 space-separated integers $ u $ and $ v $ $ (1 \le u,v \le n) $ which means there's an edge between $ u $ and $ v $ .

输出格式

Output one integer, the minimum possible value for $ w $ .

输入输出样例

输入样例 #1

3
1 2 3
1 2
1 3

输出样例 #1

7

输入样例 #2

5
4 5 3 7 8
1 2
1 3
3 4
4 5

输出样例 #2

40

说明

In the first sample, the tree itself minimizes the value of $ w $ . In the second sample, the optimal tree is: