普通的线段树合并。

其中线段树的数组 T[kN*600] 该如何计算

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>

#define LL long long
#define PR pair<LL,LL>

using namespace std;

const int kN=1e5+5;

struct Smt{
	int s[2],siz;
	#define Son(p,k) T[p].s[k]
	#define Siz(p) T[p].siz
}T[kN*600];

int n,m;
int to[kN<<1],nex[kN<<1],head[kN],tot;
int f[kN][30],rt[kN],_2[30],dep[kN],cnt;
int ans[kN];

void Add(int u,int v){
	to[++tot]=v;nex[tot]=head[u];head[u]=tot;
}

void Dfs1(int x,int fa,int depth){
	f[x][0]=fa;dep[x]=depth;
	for(int i=head[x];i;i=nex[i]){
		int ar=to[i];
		if(ar==fa){continue;}
		Dfs1(ar,x,depth+1);
	}
}

int Lca(int x,int y){
	if(dep[x]<dep[y]){swap(x,y);}
	for(int i=20;i>=0;--i){
		if(dep[x]-_2[i]>=dep[y]){
			x=f[x][i];
		}
	}
	if(x==y){return x;}
	for(int i=20;i>=0;--i){
		if(dep[x]-_2[i]>0&&f[x][i]!=f[y][i]){
			x=f[x][i];y=f[y][i];
		}
	}
	return f[x][0];
}

void Modify(int l,int r,int k,int v,int &p){
	if(!p){p=++cnt;}
	if(l==r){
		Siz(p)+=v;
		return;
	}
	int mid=(l+r)>>1;
	if(k<=mid){Modify(l,mid,k,v,Son(p,0));}
	else{Modify(mid+1,r,k,v,Son(p,1));}
	Siz(p)=max(Siz(Son(p,0)),Siz(Son(p,1)));
}

void Merge(int &p,int q){
	if(!p){p=q;return;}
	if(!q){return;}
	Merge(Son(p,0),Son(q,0));
	Merge(Son(p,1),Son(q,1));
	if(!Son(p,0)&&!Son(p,1)){
		Siz(p)+=Siz(q);return;
	}
	Siz(p)=max(Siz(Son(p,0)),Siz(Son(p,1)));
}

int Query(int l,int r,int p){
	if(l==r){return l;}
	int mid=(l+r)>>1;
	if(Siz(Son(p,0))>=Siz(Son(p,1))){return Query(l,mid,Son(p,0));}
	else{return Query(mid+1,r,Son(p,1));}
}

void Dfs2(int x,int fa){
	for(int i=head[x];i;i=nex[i]){
		int ar=to[i];
		if(ar==fa){continue;}
		Dfs2(ar,x);
		Merge(rt[x],rt[ar]);
	}
	if(Siz(rt[x])){
		ans[x]=Query(1,kN,rt[x]);
	}
}

signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;++i){
		int u,v;scanf("%d%d",&u,&v);
		Add(u,v);Add(v,u);
	}
	Dfs1(1,0,1);
	_2[0]=1;
	for(int i=1;i<=20;++i){_2[i]=_2[i-1]*2;}
	for(int i=1;_2[i]<=n;++i){
		for(int j=1;j<=n;++j){
			if(dep[j]<=_2[i]){continue;}
			f[j][i]=f[f[j][i-1]][i-1];
		}
	}
	while(m--){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		int lca=Lca(x,y);
		Modify(1,kN,z,1,rt[x]);Modify(1,kN,z,1,rt[y]);
		Modify(1,kN,z,-1,rt[lca]);Modify(1,kN,z,-1,rt[f[lca][0]]);
	}
	Dfs2(1,0);
	for(int i=1;i<=n;++i){
		printf("%d\n",ans[i]);
	}
	return 0;
}