问题1553--Defending Plan Support

1553: Defending Plan Support

时间限制: 1 Sec  内存限制: 64 MB
提交: 143  解决: 34
[状态] [讨论版] [提交] [命题人:]
题目描述
The architectural structure of the college is strange, but the rule is that there is only one simple path between every two classrooms. Now the battle between Class A and Class F broke out. As a support staff of Class F, you have to go to every fight in time to help out. With the help of icebound, Class F know the probability of each classroom being attacked. So we define an important degree for each classroom. Now ask you to find a classroom x in n classrooms as your resting base which has the minimum F(x). F(x) = ∑ w(i) × d(x, i), d is the distance between x and i.
输入
he first line is an integer n,which is the number of classrooms.
Then n-1 lines follow. Each line has three numbers x,y,z. There is a road of meters between x and y.
The last line contains n numbers. The i‑th number w(i) is the important degree of the classroom.
2 ≤ n ≤ 5 × 105, 0 ≤ z, wi ≤ 1000,1 ≤ x, y ≤ n
输出
Output a line with an integer, representing the minimum F(x).
样例输入 Copy
5
1 2 1
2 3 1
2 4 1
3 5 6
2 3 1 8 7
样例输出 Copy
60
来源/分类