非常显然的一道树剖
用线段树维护区间为1区间为0
因为修改只有在根到节点
甚至不用维护深度
因为一开始节点都为0
甚至不用线段树的 build 操作
比模板还简单...
至于询问修改了多少就只要把修改后的数量减去修改前的数量
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7; int n,m; vector <int> v[N]; int fa[N],son[N],sz[N];//甚至不用维护深度 inline void dfs1(int x,int f) { fa[x]=f; sz[x]=1; int mxsz=0,len=v[x].size(); for(int i=0;i<len;i++) { int u=v[x][i]; if(u==f) continue; dfs1(u,x); sz[x]+=sz[u]; if(sz[u]>mxsz) { mxsz=sz[u]; son[x]=u; } } } int Top[N],id[N],cnt; inline void dfs2(int x,int topp) { id[x]=++cnt; Top[x]=topp; if(!son[x]) return; dfs2(son[x],topp); int len=v[x].size(); for(int i=0;i<len;i++) { int u=v[x][i]; if(u==fa[x]||u==son[x]) continue; dfs2(u,u); } } //----------------------线段树-------------------------- //甚至没有build函数 int t[N<<2],add[N<<2],clr[N<<2];//add和clr为懒标记 inline void push(int &o,int &l,int &r)//下传懒标记 { int lc=o<<1,rc=o<<1|1,mid=l+r>>1; if(clr[o])//区间为0 { add[lc]=add[rc]=0; t[lc]=t[rc]=0; clr[lc]=clr[rc]=1; clr[o]=0; } if(add[o])//区间为1 { add[lc]=1; add[rc]=1; t[lc]=mid-l+1; t[rc]=r-mid; add[o]=0; } } void Add(int o,int l,int r,int ql,int qr)//区间修改为1 { if(l>=ql&&r<=qr) { add[o]=1; t[o]=r-l+1; return; } push(o,l,r); int mid=l+r>>1; if(ql<=mid) Add(o<<1,l,mid,ql,qr); if(qr>mid) Add(o<<1|1,mid+1,r,ql,qr); t[o]=t[o<<1]+t[o<<1|1]; } void Clr(int o,int l,int r,int ql,int qr)//区间清0 { if(l>=ql&&r<=qr) { add[o]=t[o]=0; clr[o]=1; return; } push(o,l,r); int mid=l+r>>1; if(ql<=mid) Clr(o<<1,l,mid,ql,qr); if(qr>mid) Clr(o<<1|1,mid+1,r,ql,qr); t[o]=t[o<<1]+t[o<<1|1]; } int query(int o,int l,int r,int ql,int qr)//询问区间和 { if(l>=ql&&r<=qr) return t[o]; push(o,l,r); int mid=l+r>>1,res=0; if(ql<=mid) res+=query(o<<1,l,mid,ql,qr); if(qr>mid) res+=query(o<<1|1,mid+1,r,ql,qr); t[o]=t[o<<1]+t[o<<1|1]; return res; } //---------------------线段树------------------------- void Ins(int x)//安装一个软件 { int res=0; while(x)//给根到节点的一条链安装软件，根为0号节点 { res-=query(1,1,n,id[Top[x]],id[x]);//先记录一下安装前的状态 Add(1,1,n,id[Top[x]],id[x]); res+=query(1,1,n,id[Top[x]],id[x]);//再加上安装后的状态 x=fa[Top[x]]; } res-=query(1,1,n,id[Top[x]],id[x]); Add(1,1,n,1,1);//注意最后还要考虑给根节点安装 res+=query(1,1,n,id[Top[x]],id[x]); printf("%d ",res); } void Uni(int x)//卸载一个软件 { printf("%d ", query(1,1,n,id[x],id[x]+sz[x]-1) ); Clr(1,1,n,id[x],id[x]+sz[x]-1);//直接把整个子树清空就好了 } int main() { int a; n=read(); for(int i=1;i<n;i++) { a=read(); v[a].push_back(i); } dfs1(0,0); dfs2(0,0); m=read(); char ch[10]; for(int i=1;i<=m;i++) { scanf("%s",ch); a=read(); if(ch[0]=='i') Ins(a); else Uni(a); } return 0; }