LGP11993 [JOIST 2025] 迁移计划 学习笔记
\(\texttt{Luogu Link}\)
前言
线段树合并入门题。
题意简述
给定一个 \(n\) 个结点、以 \(1\) 为根的无权树。称一个点 \(u\) 的危险度 \(d_u\) 为 \(\text{dis}(1,u)\)。接下来需要执行三种操作共 \(m\) 次：
1 x y：对于所有满足 \(d_u=x\) 的点 \(u\)，令其能唯一达到的那个 \(d_v=y\) 的点为 \(v\)，则 \(w_v\gets w_u+w_v\)，\(w_u\gets 0\)。保证 \(y<x\)。2 u x：\(w_u\gets w_u+x\)。3 u：回答当前的 \(w_u\)。
\(n,m\le 2\times 10^6\)。
做法解析
对于暴力来说，实际数据规模最大至少可以卡到 \(O(m\sqrt{n})\) 附近。咋优化呢？
“可加信息的整体迁移”，想线段树合并（此题的“可加”体现在，对于一对父子 \(u,v\)，我们 \(v\) 的信息通过 \(\text{dfs}\) 序容易被 \(u\) 统计求和）。我们选择对每个深度开一个线段树（下标对应 \(\text{dfs}\) 序），然后每次把某个深度合并到另一个深度直接合并即可。线段树合并的复杂度理应是对的。
代码实现
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=2e6+5;
int N,X,Opt,M,W[MaxN],Y;
vector<int> Tr[MaxN];
int dfn[MaxN],dcnt,dep[MaxN],siz[MaxN];
void dfs(int u){dfn[u]=++dcnt,siz[u]=1;for(int v : Tr[u])dep[v]=dep[u]+1,dfs(v),siz[u]+=siz[v];
}
int srt[MaxN];
struct SegTrees{int val[MaxN<<5],ls[MaxN<<5],rs[MaxN<<5],tot;void pushup(int u){val[u]=val[ls[u]]+val[rs[u]];}void modify(int &u,int cl,int cr,int dd,int x){if(!u)u=++tot;if(cl==cr){val[u]+=x;return;}int cmid=(cl+cr)>>1;if(dd<=cmid)modify(ls[u],cl,cmid,dd,x);else modify(rs[u],cmid+1,cr,dd,x);pushup(u);}int query(int u,int cl,int cr,int dl,int dr){if(!u)return 0;int res=0;if(dl<=cl&&cr<=dr)return val[u];int cmid=(cl+cr)>>1;if(dl<=cmid)res+=query(ls[u],cl,cmid,dl,dr);if(dr>cmid)res+=query(rs[u],cmid+1,cr,dl,dr);return res;}int merge(int u,int v,int cl,int cr){if(!u||!v)return u|v;if(cl==cr){val[u]+=val[v];return u;}int cmid=(cl+cr)>>1;ls[u]=merge(ls[u],ls[v],cl,cmid);rs[u]=merge(rs[u],rs[v],cmid+1,cr);pushup(u);return u;}
}SgS;
int main(){readi(N);for(int i=2;i<=N;i++)readi(X),Tr[X].push_back(i);for(int i=1;i<=N;i++)readi(W[i]);dfs(1);for(int i=1;i<=N;i++)SgS.modify(srt[dep[i]],1,N,dfn[i],W[i]);readi(M);for(int i=1;i<=M;i++){readi(Opt);if(Opt==1){readis(X,Y);srt[Y]=SgS.merge(srt[Y],srt[X],1,N);srt[X]=0;}if(Opt==2){readis(X,Y);SgS.modify(srt[dep[X]],1,N,dfn[X],Y);}if(Opt==3){readi(X);writil(SgS.query(srt[dep[X]],1,N,dfn[X],dfn[X]+siz[X]-1));}}return 0;
}