时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
有N座城市,编号为1~N,它们通过N-1条边相连,形成一棵树。某天从外地来了马戏团,他们计划安排M次演出,每次从x城市到y城市的路径上(包括x城市和y城市)都能看到他们的表演,他们给每场表演的节目取了个代号,例如某场表演节目为z(z是正整数)。假设他们每次演出只表演一个节目,请问M场表演完之后,每座城市看的最多的节目编号是什么?
(编号相同的节目是同一个节目)
输入描述:
第一行数字N,M。
接下来N-1行,每行两个数字a,b,表示城市a与城市b间有一条边。
再接下来M行,每行三个数字x,y,z.如题。
1<=N,M<=100000
1<=a,b,x,y<=N
1<=z<=109
输出描述:
输出有N行。
每i行的数字表示第i个城市看的最多的节目编号,如果有并列,输出编号最小的。如果某个城市没有观看任何节目,则输出0。
示例1
输入
复制
20 50
8 6
10 6
18 6
20 10
7 20
2 18
19 8
1 6
14 20
16 10
13 19
3 14
17 18
11 19
4 11
15 14
5 18
9 10
12 15
11 14 87
12 1 87
14 3 84
17 2 36
6 5 93
17 6 87
10 14 93
5 16 78
6 15 93
15 5 16
11 8 50
17 19 50
5 4 87
15 20 78
1 17 50
20 13 87
7 15 22
16 11 94
19 8 87
18 3 93
13 13 87
2 1 87
2 6 22
5 20 84
10 12 93
18 12 87
16 10 93
8 17 93
14 7 36
7 4 22
5 9 87
13 10 16
20 11 50
9 16 84
10 17 16
19 6 87
12 2 36
20 9 94
9 2 84
14 1 94
5 5 94
8 17 16
12 8 36
20 17 78
12 18 50
16 8 94
2 19 36
10 18 36
14 19 50
4 12 50
输出
复制
87
36
84
22
87
87
22
50
84
87
50
36
87
93
36
94
16
87
50
50