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:
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1088F/8dcff1bd3592f8428b954bbf8127dd97feb4ff38.png)