25pts WA 求条
查看原帖
25pts WA 求条
744534
MitchellZhong楼主2025/7/30 08:30
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> g[5000005];
int fa[5000005][25];
int dep[5000005];
struct node{
	int ls,rs,tp,siz;
};
node Tr[5000005];
int cnt=0;
int rt[5000005];
void dfs(int u,int f){
	fa[u][0]=f;
	for(int i=1;i<=20;i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	dep[u]=dep[f]+1;
	for(auto v : g[u]){
		if(v==f){
			continue;
		}
		dfs(v,u);
	}
}
int lca(int u,int v){
	if(dep[u]>dep[v]){
		swap(u,v);
	}
	for(int i=20;i>=0;i--){
		if(dep[fa[v][i]]>=dep[u]){
			v=fa[v][i];
		}
	}
	if(u==v){
		return u;
	}
	for(int i=20;i>=0;i--){
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}
void pushup(int u){
	if(Tr[Tr[u].ls].siz>=Tr[Tr[u].rs].siz){
		Tr[u].siz=Tr[Tr[u].ls].siz;
		Tr[u].tp=Tr[Tr[u].ls].tp;
	}else{
		Tr[u].siz=Tr[Tr[u].rs].siz;
		Tr[u].tp=Tr[Tr[u].rs].tp;
	}
}
void update(int & rt,int l,int r,int p,int x){
	if(!rt){
		rt=++cnt;
	}
	if(l==r){
		Tr[rt].siz+=x;
		Tr[rt].tp=p;
		return ;
	}
	int mid=l+r>>1;
	if(p<=mid){
		update(Tr[rt].ls,l,mid,p,x);
	}else{
		update(Tr[rt].rs,mid+1,r,p,x);
	}
	pushup(rt);
}
int merge(int x,int y,int l,int r){
	if(!x || !y){
		return max(x,y);
	}
	if(l==r){
		Tr[x].siz+=Tr[y].siz;
		return x;
	}
	int mid=l+r>>1;
	Tr[x].ls=merge(Tr[x].ls,Tr[y].ls,l,mid);
	Tr[x].rs=merge(Tr[x].rs,Tr[y].rs,mid+1,r);
	pushup(x);
	return x;
}
int ans[5000005];
void dfs2(int u,int f){
	for(auto v : g[u]){
		if(v==f){
			continue;
		}
		dfs2(v,u);
		rt[u]=merge(rt[u],rt[v],1,n);
	}
	ans[u]=Tr[rt[u]].siz ? Tr[rt[u]].tp : 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		update(rt[a],1,n,c,1);
		update(rt[b],1,n,c,1);
		int lcaa=lca(a,b);
		update(rt[lcaa],1,n,c,-1);
		update(rt[fa[lcaa][0]],1,n,c,-1);
	}
	dfs2(1,0);
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}
2025/7/30 08:30
加载中...