终于来补线段树合并了，之前本来打算写的，结果懒了。

前置知识

  • 动态开点线段树

算法操作

就是对于每个点维护一颗不全的线段树，对于每个节点记录其对应线段树的根节点。对于需要其子树贡献的节点，自下而上合并线段树，再查询。

很显然，和 Dsu on tree 是同类的算法.

具体实现

我们只需要知道线段树的合并即可，线段树大家再熟悉不过了吧。

我们考虑在叶子结点的时候将两线段树的节点信息合并，具体如何合并我们视题目而定。如果题目保证不再访问合并前的线段树，我们可以将其中一颗树作为载体合并，这样可以节约空间。对于其中一颗子树没有的节点，我们直接把它嫁接过来就可以了。

代码实现，和其他数据结构合并有异曲同工之妙:

	int merge(int x,int y){
		if(!x||!y) return x|y;
		if(t[x].l==t[x].r){
			t[x].cnt+=t[y].cnt;
			update(x);
			return x;
		}
		lc(x)=merge(lc(x),lc(y));
		rc(x)=merge(rc(x),rc(y));
		pushup(x);
		return x;
	}

好那么看具体的例题应用。

例题应用

我们拿模板题来。雨天的尾巴

这题我们直接架树上差分，然后上线段树合并，上面的讲述的代码体现如下:

#include<bits/stdc++.h>
using namespace std;
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define LL long long
#define N 100000+3
#define MAXN 100000
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();}
	return s*f;
}
inline void Swap(int &x,int &y){
	int tmp=x;x=y;y=tmp;
}
inline int Max(int x,int y){
	return x>y?x:y;
}
inline int Min(int x,int y){
	return x>y?y:x;
}
int n,m; 
vector<int>head,to,nxt;
void join(int u,int v){
	nxt.push_back(head[u]);
	head[u]=to.size();
	to.push_back(v);
}
int fa[N][20+3],dep[N];
void dfs1(int u,int f){
	dep[u]=dep[f]+1;
	for(int i=0;i<20;++i){
		fa[u][i+1]=fa[fa[u][i]][i];
	}
	for(int i=head[u];~i;i=nxt[i]){
		if(to[i]==f) continue;
		fa[to[i]][0]=u;
		dfs1(to[i],u);
	}
}
int LCA(int x,int y){
	if(dep[x]<dep[y]) Swap(x,y);
	for(int i=20;i>=0;--i){
		if(dep[fa[x][i]]>=dep[y])
			x=fa[x][i];
		if(x==y) return x;
	}
	for(int i=20;i>=0;--i){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int rt[N];
struct SegTree{
	#define lc(x) t[x].lc
	#define rc(x) t[x].rc
	int tot;
	struct Node{
		int l,r,mid;
		int lc,rc;
		int cnt,mxcnt,mxans;
	}t[N<<6];
	SegTree(){
		tot=0;
	}
	inline void pushup(int i){
		t[i].cnt=(t[lc(i)].cnt+t[rc(i)].cnt);
		t[i].mxcnt=Max(t[lc(i)].mxcnt,t[rc(i)].mxcnt);
		if(t[lc(i)].mxcnt>t[rc(i)].mxcnt){
			t[i].mxans=t[lc(i)].mxans;
		}else if(t[lc(i)].mxcnt<t[rc(i)].mxcnt){
			t[i].mxans=t[rc(i)].mxans;
		}else{
			t[i].mxans=Min(t[lc(i)].mxans,t[rc(i)].mxans);
		}
	}
	inline void update(int i){
		if(t[i].l!=t[i].r) return;
		if(t[i].cnt) t[i].mxcnt=t[i].cnt,t[i].mxans=t[i].l;
		else t[i].mxcnt=t[i].mxans=0;
	}
	void ins(int &i,int l,int r,int p,int k){
		if(!i){
			i=++tot;
			t[i].l=l;t[i].r=r;t[i].mid=(l+r)>>1;
			t[i].cnt=t[i].lc=t[i].rc=0;
			t[i].mxcnt=t[i].mxans=0;
		}
		if(p==t[i].l&&t[i].r==p){
			t[i].cnt+=k;
			update(i);
			return;
		}
		if(p<=t[i].mid) ins(lc(i),l,t[i].mid,p,k);
		if(t[i].mid+1<=p) ins(rc(i),t[i].mid+1,r,p,k);
		pushup(i);
	}
	int merge(int x,int y){
		if(!x||!y) return x|y;
		if(t[x].l==t[x].r){
			t[x].cnt+=t[y].cnt;
			update(x);
			return x;
		}
		lc(x)=merge(lc(x),lc(y));
		rc(x)=merge(rc(x),rc(y));
		pushup(x);
		return x;
	}
	#undef lc
	#undef rc
}t;
int ans[N];
void dfs(int u){
	for(int i=head[u];~i;i=nxt[i]){
		if(to[i]==fa[u][0]) continue;
		dfs(to[i]);
		rt[u]=t.merge(rt[u],rt[to[i]]);
	}
	ans[u]=t.t[rt[u]].mxcnt?t.t[rt[u]].mxans:0;
}
int main(){
	n=read();m=read();
	head.resize(n+1,-1);
	for(int i=1;i<n;++i){
		int u=read(),v=read();
		join(u,v);join(v,u);
	}
	dfs1(1,1);
	for(int i=1;i<=m;++i){
		int x=read(),y=read(),z=read();
		int f=LCA(x,y);
		int npc;
		t.ins(rt[x],1,MAXN,z,1);
		t.ins(rt[y],1,MAXN,z,1);
		t.ins(rt[f],1,MAXN,z,-1);
		t.ins(rt[fa[f][0]],1,MAXN,z,-1);
	} 
	dfs(1);
	for(int i=1;i<=n;++i){
		printf("%d\n",ans[i]);
	}
	return 0;
}