提交: 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 **z **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 × 10**^{5}, 0 ≤ z, wi ≤ 1000,1 ≤ x, y ≤ n

Then

The last line contains

2

输出

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`

来源/分类