线段树合并15pts求调
查看原帖
线段树合并15pts求调
572133
潘德理2010楼主2023/11/23 23:47
#include<bits/stdc++.h>
using namespace std;
struct st_table{// st 表 
	int f[200010][20],s;
	int que(int x,int y){ // 查询 x 到 y 的区间内的最小值 
		if(x==y) return f[x][0];
		if(x>y) swap(x,y);
		int d=log2(y-x);
		return min(f[x][d],f[y-(1<<d)+1][d]);
	}
	void init(queue<int> q){// st 表初始化 
		while(!q.empty()){
			f[++s][0]=q.front();
			q.pop();
		}
		for(int i=2,k=1;i<s;i*=2,k++){
			for(int j=1;j+i-1<=s;j++){
				f[j][k]=que(j,j+i-1);
			}
		}
	}
}st;
struct sgt{
	int ls,rs,val,sum,ans;
};
struct merge_abled_sgt{//线段树合并 
	sgt f[3200010];
	int cnt;
	void pushup(int x){
		int ls=f[x].ls,rs=f[x].rs;
		if(f[ls].sum>f[rs].sum){
			f[x].sum=f[ls].sum;
			f[x].ans=f[ls].ans;
		}
		else if(f[rs].sum>f[ls].sum){
			f[x].sum=f[rs].sum;
			f[x].ans=f[rs].ans;
		}
		else{
			f[x].sum=f[ls].sum;
			f[x].ans=min(f[ls].ans,f[rs].ans);
		}
	}
	int add(int u,int le,int ri,int x,int k){//插入 k 个点,权值为 x 
		if(!u) u=++cnt;
		if(le==ri){
			f[u].sum+=k;
			f[u].ans=x;
			return u;
		}
		int mid=(le+ri)/2;
		if(x<=mid) f[u].ls=add(f[u].ls,le,mid,x,k);
		else f[u].rs=add(f[u].rs,mid+1,ri,x,k);
		pushup(u);
		return u;
	}
	int meg(int x,int y,int le,int ri){//合并树 y 至树 x 
		if(!x) return y;
		if(!y) return x;		
		if(le==ri){
			f[x].sum+=f[y].sum;
			f[x].ans=le;
			return x;
		}
		int mid=(le+ri)/2;
		f[x].ls=meg(f[x].ls,f[y].ls,le,mid);
		f[x].rs=meg(f[x].rs,f[y].rs,mid+1,ri);
		pushup(x);
		return x;
	}
}tr;
int rt[100010];//每棵树的树根 
queue<int> r;
vector<int> e[100010];//邻接表 
int n,q,a,b,z,l,fa[100010];//fa[i] 为 i 的父亲 
int p[100010],d[100010],c[100010],t;
//p[]欧拉序 ,d[]为 dfs 序 ,c[i] 表示 dfs 序为 i 的数 
void dfs1(int u,int f){//搜索确定欧拉序 
	fa[u]=f;
	d[u]=++t;
	r.push(d[u]);
	p[u]=r.size();
	c[d[u]]=u;
	for(int i=0;i<int(e[u].size());i++){
		int v=e[u][i];
		if(v==f) continue;
		dfs1(v,u);
		r.push(d[u]);
	}
}
int lca(int x,int y){
	return c[st.que(p[x],p[y])];
}
void dfs2(int u,int f){//搜索 & 合并树 
	for(int i=0;i<int(e[u].size());i++){
		int v=e[u][i];
		if(v==f) continue;
		dfs2(v,u);
		rt[u]=tr.meg(rt[u],rt[v],1,n);
	}
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}	
	dfs1(1,0);
	st.init(r);
	while(q--){
		scanf("%d%d%d",&a,&b,&z);
		rt[a]=tr.add(rt[a],1,n,z,1);//加点 
		rt[b]=tr.add(rt[b],1,n,z,1);
		l=lca(a,b);
		rt[l]=tr.add(rt[l],1,n,z,-1);
		if(l!=1) rt[fa[l]]=tr.add(rt[fa[l]],1,n,z,-1);
	}
	dfs2(1,0);
	for(int i=1;i<=n;i++) printf("%d\n",tr.f[rt[i]].ans);
} 
2023/11/23 23:47
加载中...