首页 > 题解 > bzoj 3307 雨天的尾巴

bzoj 3307 雨天的尾巴

Description

N个点,形成一个树状结构。有M次发放,每次选择两个点x,y
对于x到y的路径上(含x,y)每个点发一袋Z类型的物品。完成
所有发放后,每个点存放最多的是哪种物品。

Input

第一行数字N,M
接下来N-1行,每行两个数字a,b,表示a与b间有一条边
再接下来M行,每行三个数字x,y,z.如题

Output

输出有N行
每i行的数字表示第i个点存放最多的物品是哪一种,如果有
多种物品的数量一样,输出编号最小的。如果某个点没有物品
则输出0

Sample Input

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

Sample Output

87

36

84

22

87

87

22

50

84

87

50

36

87

93

36

94

16

87

50

50

1<=N,M<=100000

1<=a,b,x,y<=N

1<=z<=10^9

题解

对于每个点都维护一棵权值线段树,然后将标记差分,最后将每个节点的线段树与父亲节点的线段树合并即可。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×