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

· · 题解

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

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

时间复杂度 O(n+m)\log n。

#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;
}