题解：P11993 [JOIST 2025] 迁移计划

看到深度相关肯定会想到 bfs 序，每次就是把一段区间里面的数加到另一段区间里面。但是你会发现由于是比较整体的一个操作，所以你维护这个 bfs 序其实是没啥用的。所以考虑对于每个深度整体维护一个集合。

这样子每次就是集合合并累加的过程。考虑对于每个深度维护一个线段树，下标为 dfs 序，向上合并就使用线段树合并。然后对于单点查询就是直接对于该深度进行 dfs 序子树查询即可。

时间复杂度

O(n+m)\log n

。

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=2e6+10;
int rt[maxn],c[maxn],dep[maxn],n,m;
int dfn[maxn],sz[maxn],id[maxn],cnt=0;
vector<int> G[maxn];
struct SegmentTree{
	#define mid (l+r>>1)
	int val[maxn*32],ls[maxn*32],rs[maxn*32],tot=0;
	void pushup(int p){ val[p]=val[ls[p]]+val[rs[p]]; }
	void modify(int& p,int l,int r,int x,int v){
		if(!p) p=++tot;
		if(l==r){ val[p]+=v; return ; }
		if(x<=mid) modify(ls[p],l,mid,x,v);
		else modify(rs[p],mid+1,r,x,v);
		pushup(p);
	}
	int query(int p,int l,int r,int ql,int qr){
		if(!p) return 0; int res=0;
		if(ql<=l&&r<=qr) return val[p];
		if(ql<=mid) res+=query(ls[p],l,mid,ql,qr); 
		if(qr>mid) res+=query(rs[p],mid+1,r,ql,qr);
		return res;
	}
	int merge(int p,int q,int l,int r){
		if(!p||!q) return p+q;
		if(l==r){ val[p]+=val[q]; return p; }
		ls[p]=merge(ls[p],ls[q],l,mid);
		rs[p]=merge(rs[p],rs[q],mid+1,r);
		pushup(p); return p;
	}
}seg;
void dfs(int u){
	dfn[u]=++cnt; id[cnt]=u; sz[u]=1;
	for(auto v:G[u]){ 
		dep[v]=dep[u]+1; 
		dfs(v); sz[u]+=sz[v]; 
	}
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=2;i<=n;i++){
		int fa; cin>>fa;
		G[fa].pb(i);
	}
	for(int i=1;i<=n;i++) cin>>c[i];
	dfs(1); cin>>m;
	for(int i=1;i<=n;i++)
		seg.modify(rt[dep[i]],1,n,dfn[i],c[i]);
	for(int i=1;i<=m;i++){
		int t; cin>>t;
		if(t==1){
			int X,Y; cin>>X>>Y;
			rt[Y]=seg.merge(rt[Y],rt[X],1,n);
			rt[X]=0;
		}else if(t==2){
			int A,L; cin>>A>>L;
			seg.modify(rt[dep[A]],1,n,dfn[A],L);
		}else{
			int B; cin>>B;
			cout<<seg.query(rt[dep[B]],1,n,dfn[B],dfn[B]+sz[B]-1)<<"\n";
		}
	}
	return 0;
}

题解：P11993 [JOIST 2025] 迁移计划

文章操作

相关推荐

评论

题解：P11993 [JOIST 2025] 迁移计划