F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 3743. -- [Coci2015]Kamp

3743: [Coci2015]Kamp

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 682  Solved: 330
[Submit][Status][Discuss]

Description

一颗树n个点,n-1条边,经过每条边都要花费一定的时间,任意两个点都是联通的。
有K个人(分布在K个不同的点)要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点出发,把这K个人分别送回去。
请你回答,对于i=1~n,如果在第i个点举行聚会,司机最少需要多少时间把K个人都送回家。

Input

第一行两个数,n,K。
接下来n-1行,每行三个数,x,y,z表示x到y之间有一条需要花费z时间的边。
接下来K行,每行一个数,表示K个人的分布。

Output

输出n个数,第i行的数表示:如果在第i个点举行聚会,司机需要的最少时间。

Sample Input

7 2
1 2 4
1 3 1
2 5 1
2 4 2
4 7 3
4 6 2
3
7

Sample Output

11
15
10
13
16
15
10

HINT

【数据规模】

K <= N <= 500000

1 <= x,y <= N, 1 <= z <= 1000000


Source

[Submit][Status][Discuss]

HOME Back