发布时间：2025-05-22

线段树合并

$m$ 次操作，每次向 $x,y$ 路径所有点发放种类为 $z$ 的一个物品

求每个节点最多的种类编号

每个节点维护一颗权值线段树

cpp

vector<int> ls,rs;
vector<int> cnt,res,dep;
vector<vector<int>> par,adj;
int newNode(int x=0){
	cnt.push_back(x);
	res.push_back(0);
	ls.push_back(0);
	rs.push_back(0);
	return cnt.size()-1;
}
void pushup(int p){
	if((cnt[ls[p]]>cnt[rs[p]])||(cnt[ls[p]]==cnt[rs[p]]&&res[ls[p]]<res[rs[p]])){
		cnt[p]=cnt[ls[p]];
		res[p]=res[ls[p]];
	}
	else{
		cnt[p]=cnt[rs[p]];
		res[p]=res[rs[p]];
	}
}
int merge(int p,int q,int l,int r){
	if(!p)return q;
	if(!q)return p;
	if(l==r){
		cnt[p]+=cnt[q];
		return p;
	}
	int mid=l+r>>1;
	ls[p]=merge(ls[p],ls[q],l,mid);
	rs[p]=merge(rs[p],rs[q],mid+1,r);
	pushup(p);
	return p;
}
int insert(int p,int l,int r,int x,int y){
	if(!p)p=newNode();
	if(l==r){
		cnt[p]+=y;
		res[p]=x;
		return p;
	}
	int mid=l+r>>1;
	if(x<=mid)ls[p]=insert(ls[p],l,mid,x,y);
	else rs[p]=insert(rs[p],mid+1,r,x,y);
	pushup(p);
	return p;
}
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	par[u][0]=fa;
	for(int i=1;i<=__lg(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
	for(auto v:adj[u]){
		if(v==fa)continue;
		dfs(v,u);
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	while(dep[u]>dep[v])u=par[u][__lg(dep[u]-dep[v])];
	if(u==v)return u;
	for(int i=__lg(dep[u]);i>=0;i--){
		if(par[u][i]!=par[v][i]){
			u=par[u][i];
			v=par[v][i];
		}
	}
	return par[u][0];
}
void solve(){
	int n,m;
	cin>>n>>m;
	newNode();
	adj.assign(n+1,{});
	par.assign(n+1,vector<int>(__lg(n)+1));	
	dep.assign(n+1,0);
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1,0);
	vector<int> root(n+1);
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		int t=lca(x,y);
		root[x]=insert(root[x],1,100000,z,1);
		root[y]=insert(root[y],1,100000,z,1);
		root[t]=insert(root[t],1,100000,z,-1);
		root[par[t][0]]=insert(root[par[t][0]],1,100000,z,-1);
	}
	vector<int> ans(n+1);
	auto cal=[&](auto&& self,int u,int fa)->void{
		for(auto v:adj[u]){
			if(v==fa)continue;
			self(self,v,u);
			root[u]=merge(root[u],root[v],1,100000);
		}
		ans[u]=res[root[u]];
		if(!cnt[root[u]])ans[u]=0;
	};
	cal(cal,1,0);
	for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";
}

线段树合并 ​

线段树合并