试题分析
数据结构板子题。其中只需要维护区间覆盖，区间查询的线段树。而这是在一棵树中，所以考虑树链剖分。
然后就真是板子了。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int N=200001; struct node{ int u,v,nex; }x[N<<1]; int cnt,head[N],n,deep[N],seg[N],rev[N],top[N],son[N],size[N],father[N]; void dfs1(int f,int fath){ size[f]=1; father[f]=fath; deep[f]=deep[fath]+1; for(int i=head[f];i!=-1;i=x[i].nex){ if(x[i].v==fath) continue; dfs1(x[i].v,f); size[f]+=size[x[i].v]; if(son[f]==-1){son[f]=x[i].v;} else if(size[x[i].v]>size[son[f]]) son[f]=x[i].v; } return; } void dfs2(int f,int fath){ if(son[f]!=-1){ seg[son[f]]=++seg[0]; rev[seg[0]]=son[f]; top[son[f]]=top[f]; dfs2(son[f],f); } for(int i=head[f];i!=-1;i=x[i].nex){ if(x[i].v==fath||son[f]==x[i].v) continue; seg[x[i].v]=++seg[0]; rev[seg[0]]=x[i].v; top[x[i].v]=x[i].v; dfs2(x[i].v,f); } } void add(int u,int v){ x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++; }int q; char str[21]; int flag[N<<1],ans[N<<1]; void pushdown(int k,int l,int r){ if(flag[k]==-1) return; int mid=l+r>>1; flag[k<<1]=flag[k<<1|1]=flag[k]; ans[k<<1]=(mid-l+1)*flag[k<<1]; ans[k<<1|1]=(r-mid)*flag[k<<1|1]; flag[k]=-1; return; } int query(int k,int l,int r,int x,int y){ if(x<=l&&r<=y) return ans[k]; pushdown(k,l,r); int mid=l+r>>1,res=0; if(x<=mid) res+=query(k<<1,l,mid,x,y); if(mid<y) res+=query(k<<1|1,mid+1,r,x,y); ans[k]=ans[k<<1]+ans[k<<1|1]; return res; } int ask_sum(int x,int y){ int fx=top[x],fy=top[y],res=0; while(fx!=fy){ if(deep[fx]<deep[fy]) swap(x,y),swap(fx,fy); res+=query(1,1,seg[0],seg[fx],seg[x]); x=father[fx];fx=top[x]; } if(deep[x]>deep[y]) swap(x,y); res+=query(1,1,seg[0],seg[x],seg[y]); return res; } void update(int k,int l,int r,int x,int y,int w){ if(x<=l&&r<=y){ flag[k]=w; ans[k]=(r-l+1)*flag[k]; return; } pushdown(k,l,r); int mid=l+r>>1; if(x<=mid) update(k<<1,l,mid,x,y,w); if(mid<y) update(k<<1|1,mid+1,r,x,y,w); ans[k]=ans[k<<1]+ans[k<<1|1]; return; } void change(int x,int y,int w){ int fx=top[x],fy=top[y]; while(fx!=fy){ if(deep[fx]<deep[fy]) swap(x,y),swap(fx,fy); update(1,1,seg[0],seg[fx],seg[x],w); x=father[fx],fx=top[x]; } if(deep[x]>deep[y]) swap(x,y); update(1,1,seg[0],seg[x],seg[y],w); return; } int main(){ // freopen("1.in","r",stdin); memset(son,-1,sizeof(son)); memset(flag,-1,sizeof(flag)); memset(head,-1,sizeof(head)); n=read(); for(int i=2;i<=n;i++){ int v=read();v++; add(i,v),add(v,i); } dfs1(1,0); seg[1]=seg[0]=rev[1]=top[1]=1; dfs2(1,0); q=read(); while(q--){ scanf("%s",str+1); if(str[1]=='i'){ int x=read(); x++; int Ask=ask_sum(1,x); printf("%d ",deep[x]-Ask); change(1,x,1); } if(str[1]=='u'){ int x=read(); x++; int sum=query(1,1,seg[0],seg[x],seg[x]+size[x]-1); printf("%d ",sum); update(1,1,seg[0],seg[x],seg[x]+size[x]-1,0); } } return 0; }