[Vani有约会]雨天的尾巴

题目背景
深绘里一直很讨厌雨天。
灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。
虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。
无奈的深绘里和村民们只好等待救济粮来维生。
不过救济粮的发放方式很特别。

题目描述
首先村落里的一共有n座房屋，并形成一个树状结构。然后救济粮分m次发放，每次选择两个房屋(x,y)，然后对于x到y的路径上（含x和y)每座房子里发放一袋z类型的救济粮。
然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

输入格式
第一行两个正整数n,m，含义如题目所示。
接下来n-1行，每行两个数(a,b)，表示(a,b)间有一条边。
再接下来m行，每行三个数(x,y,z)，含义如题目所示。

输出格式
n行，第i行一个整数，表示第i座房屋里存放的最多的是哪种救济粮，如果有多种救济粮存放次数一样，输出编号最小的。
如果某座房屋里没有救济粮，则对应一行输出0。

输入输出样例
输入 #1复制
5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3
输出 #1复制
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

本来就是简单的树剖+线段树合并+树上差分，但是x写成i，，TLE成sb。

这道题每次放一个区间，不难想到需要树上差分，然后每个点都需要合并，故我们要使用线段树合并。

然后树剖求一下lca就行了。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,M=N*80;
int n,m,res[N],len;
int rt[N],mx[M],t[M],lc[M],rc[M],cnt;
int bl[N],f[N],sz[N],h[N],son[N],vis[N];
int head[N],nex[N<<1],to[N<<1],tot;
inline int read(){
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();   return x;
}
inline void add(int a,int b){to[++tot]=b; nex[tot]=head[a]; head[a]=tot;}
void dfs1(int x){
	sz[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(f[x]==to[i])	continue;
		h[to[i]]=h[x]+1;	f[to[i]]=x;
		dfs1(to[i]);	sz[x]+=sz[to[i]];
		if(sz[to[i]]>sz[son[x]])	son[x]=to[i];
	}
}
void dfs2(int x,int belong){
	bl[x]=belong;
	if(!son[x])	return ; dfs2(son[x],belong);
	for(int i=head[x];i;i=nex[i])
		if(h[to[i]]>h[x]&&to[i]!=son[x])	dfs2(to[i],to[i]);
}
inline int lca(int x,int y){
	while(bl[x]!=bl[y]){
		if(h[bl[x]]<h[bl[y]])	swap(x,y);	x=f[bl[x]];
	}
	return h[x]>h[y]?y:x;
}
inline void push_up(int p){
	if(mx[lc[p]]>=mx[rc[p]])	mx[p]=mx[lc[p]],t[p]=t[lc[p]];
	else	mx[p]=mx[rc[p]],t[p]=t[rc[p]];
}
void change(int &p,int l,int r,int x,int v){
	if(x<l||x>r)	return ;
	if(!p)	p=++cnt;
	if(l==r){mx[p]+=v; t[p]=x; return ;}
	int mid=l+r>>1;
	if(x<=mid)	change(lc[p],l,mid,x,v);
	else	change(rc[p],mid+1,r,x,v);
	push_up(p);
}
int merge(int x,int y,int l,int r){
	if(!x||!y)	return x^y;
	if(l==r){mx[x]+=mx[y]; t[x]=l; return x;}
	int mid=l+r>>1;
	lc[x]=merge(lc[x],lc[y],l,mid);
	rc[x]=merge(rc[x],rc[y],mid+1,r);
	push_up(x);
	return x;
}
void dfs(int x){
	for(int i=head[x];i;i=nex[i]){
		if(h[to[i]]<h[x])	continue;
		dfs(to[i]); rt[x]=merge(rt[x],rt[to[i]],1,len);
	}
	if(mx[rt[x]])	res[x]=t[rt[x]];
}
signed main(){
	n=read(),m=read();
	for(int i=1,a,b;i<n;i++)	a=read(),b=read(),add(a,b),add(b,a);
	dfs1(1);	dfs2(1,1);
	len=100000;
	for(int i=1,x,y,z;i<=m;i++){
		x=read(),y=read(),z=read();
		int fa=lca(x,y);
		change(rt[x],1,len,z,1),change(rt[y],1,len,z,1);
		change(rt[fa],1,len,z,-1);
		if(f[fa])	change(rt[f[fa]],1,len,z,-1);
	}
	dfs(1);
	for(int i=1;i<=n;i++)	printf("%d\n",res[i]);
	return 0;
}