6302 雨天的尾巴 0x60「图论」例题
背景
深绘里一直很讨厌雨天。
灼热的天气穿透了前半个夏天,后来一场大雨和随之而来的洪水,浇灭了一切。
虽然深绘里家乡的小村落对洪水有着顽固的抵抗力,但也倒了几座老房子,几棵老树被连根拔起,以及田地里的粮食被弄得一片狼藉。
无奈的深绘里和村民们只好等待救济粮来维生。
不过救济粮的发放方式很特别。
描述
有 N (N≤10^5) 个点,形成一个树状结构。
有 M (M≤10^5) 次发放操作,每次选择两个点 x,y,对 x 到 y 的路径上(包括 x,y)的每个点发放一袋 z (z≤10^9) 类型的物品。
求完成所有发放操作后,每个点存放最多的是哪种类型的物品。
输入格式
第一行两个正整数n,m,含义如题目所示。
接下来n-1行,每行两个数(a,b),表示(a,b)间有一条边。
再接下来m行,每行三个数(x,y,z),含义如题目所示。
输出格式
n行,第i行一个整数,表示第i座房屋里存放的最多的是哪种救济粮,如果有多种救济粮存放次数一样,输出编号最小的。
如果某座房屋里没有救济粮,则对应一行输出0。
样例输入
5 3 1 2 3 1 3 4 5 3 2 3 3 1 5 2 3 3 3
样例输出
2 3 3 0 2
数据范围与约定
- 对于20%的数据,1 <= n, m <= 100
- 对于50%的数据,1 <= n, m <= 2000
- 对于100%的数据,1 <= n, m <= 100000, 1 <= a, b, x, y <= n, 1 <= z <= 100000
来源
Vani,Vani有约会杯邀请赛