宣官囚窕 AC on 1,4
查看原帖
宣官囚窕 AC on 1,4
590675
A1ex_5yn7ax楼主2025/7/29 10:14
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> vec[100001];
int rt[100001],ans[100001];
struct node{
	int l,r,val;
};
struct seg{
	node tr[100000007];int tot;
	void add(int &u,int l,int r,int po,int val){
		if(!u) u=++tot;
		if(l==r){tr[u].val+=val;return ;} 
		int mid=l+r>>1;
		if(po<=mid) add(tr[u].l,l,mid,po,val);
		else add(tr[u].r,mid+1,r,po,val);
		tr[u].val=max(tr[tr[u].l].val,tr[tr[u].r].val);
	}
	void mer(int r1,int r2,int l,int r){//r2合并到r1 
	    int mid=l+r>>1;
	    if(!tr[r1].l&&!tr[r1].r&&!tr[r2].l&&!tr[r2].r){tr[r1].val+=tr[r2].val;return ;}
		if(tr[r2].l&&tr[r1].l) mer(tr[r1].l,tr[r2].l,l,mid);
		if(!tr[r1].l&&tr[r2].l) tr[r1].l=tr[r2].l;
		if(tr[r2].r&&tr[r1].r) mer(tr[r1].r,tr[r2].r,mid+1,r);
		if(!tr[r1].r&&tr[r2].r) tr[r1].r=tr[r2].r;
		tr[r1].val=max(tr[tr[r1].l].val,tr[tr[r1].r].val);
	}
	int query(int u,int l,int r){
		if(l==r) return l; 
		int mid=l+r>>1;
		if(tr[tr[u].l].val>=tr[tr[u].r].val) return query(tr[u].l,l,mid);
		else return query(tr[u].r,mid+1,r);
	}
}t;
int fa[100001],dep[100001],f[100001][21];
void dfs(int u,int F){
	fa[u]=F;dep[u]=dep[F]+1;
	for(int i=0;i<vec[u].size();i++){
		int v=vec[u][i];
		if(v==F) continue;
		dfs(v,u);
	}
}
void pre(){
	for(int i=1;i<=n;i++) f[i][0]=fa[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=20;j++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
}
int lca(int u,int v){
	if(dep[v]>dep[u]) swap(u,v);
	for(int i=20;i>=0;i--){
		if(dep[f[u][i]]>=dep[v]) u=f[u][i];
	}
	if(u==v) return u;
	for(int i=20;i>=0;i--){
		if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	}
	return f[u][0];
}
void dfs2(int u,int F){
	for(int i=0;i<vec[u].size();i++){
		int v=vec[u][i];
		if(v==F) continue;
		dfs2(v,u); 
		t.mer(rt[u],rt[v],1,100000);
	} 
	if(t.tr[rt[u]].val==0) ans[u]=0;
	else ans[u]=t.query(rt[u],1,100000);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1,u,v;i<n;i++){
    	cin>>u>>v;
    	vec[u].push_back(v);vec[v].push_back(u);
	}
	dfs(1,0);
	pre();
	for(int i=1,x,y,z;i<=m;i++){
		cin>>x>>y>>z;
		t.add(rt[x],1,100000,z,1);
		t.add(rt[y],1,100000,z,1);
		int Lca=lca(x,y);
		t.add(rt[Lca],1,100000,z,-1);
		t.add(rt[fa[Lca]],1,100000,z,-1);
	}
	dfs2(1,1);
	for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
	return 0;
}
2025/7/29 10:14
加载中...