本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-01 21:30:27

其实是简单东西。

代码上唯一需要注意的点反而来自动态开点。

尽量不要把区间范围放进结构体，可能会爆空间。

模板的代码

code

const int N=1e5+5,limit=1e5;

struct edge{
	int v,nxt;
}e[N<<1];
int head[N],tott;
void add(int u,int v){e[++tott]={v,head[u]},head[u]=tott;}

struct Seg_Tree{
	struct hhh{
		int s[2];
		int mx,c;
	}t[N<<5];
	int idx;
	void pushup(int x){
		if(t[t[x].s[0]].mx>=t[t[x].s[1]].mx)
			t[x].mx=t[t[x].s[0]].mx,t[x].c=t[t[x].s[0]].c;
		else
			t[x].mx=t[t[x].s[1]].mx,t[x].c=t[t[x].s[1]].c;
	}
	void update(int x,int l,int r,int c,int a){
		if(l==r)
			t[x].mx+=a,t[x].c=c;
		else{
			if(c<=mid){
				if(!t[x].s[0])
					t[x].s[0]=++idx;
				update(t[x].s[0],l,mid,c,a);
			}else{
				if(!t[x].s[1])
					t[x].s[1]=++idx;
				update(t[x].s[1],mid+1,r,c,a);
			}
			pushup(x);
		}
	}
	int merge(int x,int y,int l,int r){
		if(!x||!y) return x+y;
		if(l==r){
			t[x].mx=t[x].mx+t[y].mx;
			return x;
		}
		t[x].s[0]=merge(t[x].s[0],t[y].s[0],l,mid);
		t[x].s[1]=merge(t[x].s[1],t[y].s[1],mid+1,r);
		pushup(x);
		return x;
	}
}T;

int fa[21][N],dep[N];
void dfs(int u,int faa){
	fa[0][u]=faa;
	dep[u]=dep[faa]+1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==faa)
			continue;
		dfs(v,u);
	}
}
void init(int n){
	for(int k=1;k<=19;k++)
		for(int i=1;i<=n;i++)
			fa[k][i]=fa[k-1][fa[k-1][i]];
}
int lca(int x,int y){
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=19;i>=0;i--)
		if(dep[fa[i][x]]>=dep[y])
			x=fa[i][x];
	if(x==y)
		return x;
	for(int i=19;i>=0;i--)
		if(fa[i][x]!=fa[i][y])
			x=fa[i][x],y=fa[i][y];
	return fa[0][x];
}

void dfs_merge(int u,int faa){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==faa)
			continue;
		dfs_merge(v,u);
		T.merge(u,v,1,limit);
	}
}

signed main(){
	int n=read(),q=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	dfs(1,0);
	init(n);
	T.idx=n;
	while(q--){
		int u=read(),v=read(),x=read();
		T.update(u,1,limit,x,1);
		T.update(v,1,limit,x,1);
		int l=lca(u,v);
		T.update(l,1,limit,x,-1);
		if(fa[0][l])
			T.update(fa[0][l],1,limit,x,-1);
	}
	dfs_merge(1,0);
	for(int i=1;i<=n;i++)
		print(T.t[i].mx==0?0:T.t[i].c),pc('\n');
	return 0;
}