#P3307. [模板]线段树合并雨天的尾巴

    ID: 2495 传统题 1000ms 128MiB 尝试: 1465 已通过: 336 难度: 6 上传者: 标签>难度分类提高+/省选-树算法树上差分LCA树上倍增数据结构动态开点线段树线段树合并线段树上二分CF2100线段树的合并

[模板]线段树合并雨天的尾巴

题目描述

有 NN 个节点,构成一棵无向树。接下来有 MM 次物品发放,每次指定两个节点 x,yx,y 和一个物品种类编号 zz。从 xx 到 yy 的唯一简单路径上的每个节点都会收到一袋 zz 类物品,包含两个端点。

发放完成后,对每个节点求收到数量最多的物品种类。若数量并列,取编号最小的种类。

输入格式

从标准输入读取。第一行是两个整数 N,MN,M。接下来 N−1N-1 行,每行两个整数 a,ba,b,表示两个节点之间的一条无向边。

再接下来 MM 行,每行三个整数 x,y,zx,y,z,表示一次发放。

输出格式

向标准输出写入 NN 行。第 ii 行输出节点 ii 收到数量最多的物品种类编号。如果节点 ii 没有收到任何物品,则输出 00。

样例 1

5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3
2
3
3
0
2

样例 2

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

数据范围

1≤N,M≤1000001\le N,M\le100000,1≤a,b,x,y≤N1\le a,b,x,y\le N,1≤z≤1091\le z\le10^9。