玄关求助!样例没过
查看原帖
玄关求助!样例没过
570957
kimi123楼主2023/11/5 17:25

qaq

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
vector <int> vc[N+10];
int rt[N+10],de[N];
int tot=1;
int f[N][22];
struct Seg{
	int zb,yb,mx,bh;
	#define zb(x) st[x].zb//left 
	#define yb(x) st[x].yb//right
	#define mx(x) st[x].mx
	#define bh(x) st[x].bh
}st[N*49];
ll ans[N+10];
void pushup(int x){
	int zb=zb(x),yb=yb(x);
	if(mx(zb)>=mx(yb)){
		mx(x)=mx(zb);
		bh(x)=bh(zb);
	}
	else if(mx(zb)<mx(yb)){
		mx(x)=mx(yb);
		bh(x)=bh(yb);
	}
} 

int merge(int p,int q,int l,int r){
	if(!p) return q;
	if(!q) return p;
	if(l==r){
		mx(p)+=mx(q);
		bh(p)=l;
		return p;
	}
	int mid=(l+r)>>1;
	zb(p)=merge(zb(p),zb(q),l,mid);
	yb(p)=merge(yb(p),yb(q),mid+1,r);
	pushup(p);
	return p;
}
int n,m;
int modify(int x,int l,int r,int pos,int k){
	if(!x) x=++tot;
	if(l==r){
		mx(x)+=k;
		bh(x)=pos;
		return x;
	}
		int mid=(l+r)>>1;
		if(pos<=mid){
			zb(x)=modify(zb(x),l,mid,pos,k);
		}
		else{
			yb(x)=modify(yb(x),mid+1,r,pos,k);
		}
		pushup(x);
		return x;
}
void dfs(int x,int fa){
	for(int i=0;i<vc[x].size();i++){
		int to=vc[x][i];
		if(to==fa) continue;
		dfs(to,x);
		merge(rt[x],rt[to],1,N);
	}
	
	ans[x]=bh(rt[x]);
	if(!mx(rt[x])) ans[x]=0;
}
int lca(int a,int b){
	if(de[a]<de[b]) swap(a,b);
	for(int i=18;i>=0;i--){
		if(de[f[a][i]]>=de[b])  a=f[a][i];
	}
	if(a==b) return a;
	for(int i=18;i>=0;i--){
		if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
	}
	return f[a][0];
}
void pre(int x,int fa){
	for(int i=0;i<vc[x].size();i++){
		int to=vc[x][i];
		if(to==fa) continue;
		de[to]=de[x]+1;
		f[to][0]=x;
		pre(to,x);
	}
}
void init(){
	de[1]=1;
	pre(1,0);
	for(int j=1;j<=18;j++){
		for(int i=1;i<=n;i++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
}
int main(){
	cin>>n>>m;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        vc[x].push_back(y);
        vc[y].push_back(x);
        
    }
	init();
    for(int i=1;i<=m;i++){
    	int x,y,z;
    	cin>>x>>y>>z;
    	rt[x]=modify(rt[x],1,n,z,1);
    	rt[y]=modify(rt[y],1,n,z,1);
    	int lc=lca(x,y);
		rt[lc]=modify(rt[lca(x,y)],1,N,z,-1);
    	if(f[lca(x,y)][0]) 
			rt[lc]=modify(rt[f[lca(x,y)][0]],1,N,z,-1);
	}
    dfs(1,0);
    for(int i=1;i<=n;i++){
    	cout<<ans[i]<<endl;
	}
    return 0;
}
2023/11/5 17:25
加载中...