线段树合并+树上差分求助
查看原帖
线段树合并+树上差分求助
541602
蒟蒻Lucas楼主2022/8/10 16:24
#include<bits/stdc++.h>
#define in read()
#define MAXN 100050
#define MAXM MAXN<<1
#define re register
using namespace std;
//namespace DEBUG {
//	inline void cerr_out(){cerr<<'\n';}
//	template<typename Head,typename... Tail>
//	inline void cerr_out(Head H,Tail... T){cerr<<' '<<H,cerr_out(T...);}
//	void debug_out() { cerr << '\n'; }
//	template <typename Head, typename... Tail>
//	void debug_out(Head H, Tail... T) { cerr << ' ' << H, debug_out(T...); }
//#define debug(...) cerr << '[' << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
//} 
//using namespace DEBUG;

struct SGT{
	int ls,rs,num,dat;
}t[MAXN<<5];
int cnt=0,ans[MAXN];

int n,m,X[MAXN],Y[MAXN],Z[MAXN],R;
int f[MAXN][33],dep[MAXN],rt[MAXN];
int nex[MAXM],first[MAXN],to[MAXM],tot=0;

inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}

int queryLCA(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(re int i=32;i>=0;i--){
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
		if(x==y) return y;
	}
	for(re int i=32;i>=0;i--)
		if(f[x][i]!=f[y][i])
			{x=f[x][i];y=f[y][i];}
	return f[x][0];
}

void prework(int u,int fa){
	dep[u]=dep[fa]+1;
	for(re int i=1;i<=32;i++)
		f[u][i]=f[f[u][i-1]][i-1];
	for(re int e=first[u];e;e=nex[e]){
		int v=to[e];
		if(v==fa)continue;
		f[v][0]=u;
		prework(v,u);
	}
}

inline void addedge(int u,int v){
	nex[++tot]=first[u];
	first[u]=tot;
	to[tot]=v;
}

inline void pushup(int p){
	if(t[t[p].ls].num>=t[t[p].rs].num)t[p].num=t[t[p].ls].num,t[p].dat=t[t[p].ls].dat;
	else t[p].num=t[t[p].rs].num,t[p].dat=t[t[p].rs].dat;
}

#define mid ((l+r)>>1)
#define L(x) t[x].ls,l,mid
#define R(x) t[x].rs,mid+1,r
int update(int p,int l,int r,int pos,int v){
	if(!p)p=++cnt;
	if(l==r){
		t[p].num+=v;
		t[p].dat=l;
		return p;
	}
	if(pos<=mid)t[p].ls=update(L(p),pos,v);
	else t[p].rs=update(R(p),pos,v);
	pushup(p);
	return p;
}

int merge(int p,int q,int l,int r){
	if(!p)return q;
	if(!q)return p;
	if(l==r){
		t[p].num+=t[q].num;
		t[p].dat=l;
		return p;
	}
	t[p].ls=merge(t[p].ls,L(q));
	t[p].rs=merge(t[p].rs,R(q));
	pushup(p);
	return p;
}

void dfs(int u,int fa){
	for(int e=first[u];e;e=nex[e]){
		int v=to[e];
		if(v==fa)continue;
		dfs(v,u);
		merge(rt[u],rt[v],1,R);
	}
	if(t[u].num==0)ans[u]=0;
	else ans[u]=t[u].dat;
}

int main(){
	n=in,m=in;
	for(re int i=1;i<=n-1;i++){
		int u=in,v=in;
		addedge(u,v);
		addedge(v,u);
	}
	
	for(re int i=1;i<=m;i++)X[i]=in,Y[i]=in,Z[i]=in,R=max(R,Z[i]);
	
	prework(1,0);
	for(re int i=1;i<=m;i++){
		int LCA=queryLCA(X[i],Y[i]);
//		debug(X[i],Y[i],LCA);
		rt[X[i]]=update(rt[X[i]],1,R,Z[i],1);
		rt[Y[i]]=update(rt[Y[i]],1,R,Z[i],1);
		rt[LCA]=update(rt[LCA],1,R,Z[i],-1);
		if(f[LCA][0]) rt[f[LCA][0]]=update(rt[f[LCA][0]],1,R,Z[i],-1);
	}
	dfs(1,0);
	for(re int i=1;i<=n;i++)cout<<ans[i]<<'\n';
	return 0;
}
2022/8/10 16:24
加载中...