3658: 种树(第一轮04)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
BLUESKY007 喜欢种树。一天，她得到了一棵n个点的树，其中节点i重量为wi 。 在种树之前， BLUESKY007 需要用起重机把树吊起。由于她只有一台起重机， 所 以她只能选择一个点作为受力点。根据 BLUESKY007 所在世界的物理知识， 吊起 一棵树需要做的功为
1 wi ⋅ disi，其中disi 表示节点i与受力点之间的距离（边 数）。
由于吊起这棵树的费用与所做的功正相关，所以 BLUESKY007 希望所做的功尽可 能小。请你帮助她求出吊起这棵树所做的功的最小值。
输入
第一行包含一个整数n，表示树的点数。
第二行包含n个整数w1, w2, … , wn ，其中wi 表示节点i的重量。
接下来的n − 1行中，每行包含两个数u, v，表示u和v两点之间有连边。
输出
一个整数，表示最小做功。
样例输入 复制
4
1 2 3 4
1 2
2 3
3 4样例输出 复制
8提示
【样例 1 输入】
4
1 2 3 4
1 2
2 3
3 4
【样例 1 输出】
8
【样例 2 输入】
4
3 2 1 4
1 2
2 3
3 4
【样例 2 输出】
12
【数据范围】
对于 45%的数据， n ≤ 1000。
对于 100%的数据， 2 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ wi ≤ 10^8, 1 ≤ u, v ≤ n, u ≠ v 。