- #include
- #include
- #include #definemaxn 100001using namespace std;
- struct TreeNodeType {
- int l,r,dis,lit,mid,flag;
- };
- structTreeNodeType tree[maxn<<2];
- struct EdgeType {
- int to,next;
- };
- structEdgeType edge[maxn<<1];
- int if_z,n,size[maxn],deep[maxn],belong[maxn];
- int flag[maxn],end[maxn],cnt,f[maxn],head[maxn];
- int Enum,m;
- char Cget;
- inline voidread_int(int&now)
- {
- now=0,if_z=1,Cget=getchar();
- while(Cget>'9'||Cget<'0')
- {
- if(Cget=='-') if_z=-1;
- Cget=getchar();
- }
- while(Cget>='0'&&Cget<='9')
- {
- now=now*10+Cget-'0';
- Cget=getchar();
- }
- now*=if_z;
- }
- inline voidedge_add(int from,int to)
- {
- edge[++Enum].to=from,edge[Enum].next=head[to],head[to]=Enum;
- edge[++Enum].to=to,edge[Enum].next=head[from],head[from]=Enum;
- }
- voidsearch(intnow,int fa)
- {
- intpos=cnt++;
- deep[now]=deep[fa]+1,f[now]=fa;
- for(inti=head[now];i;i=edge[i].next)
- {
- if(edge[i].to==fa)continue;
- search(edge[i].to,now);
- }
- size[now]=cnt-pos;
- }
- voidsearch_(intnow,int chain)
- {
- flag[now]=++cnt;
- belong[now]=chain;
- intpos=-1;
- for(inti=head[now];i;i=edge[i].next)
- {
- if(edge[i].to==f[now])continue;
- if(size[edge[i].to]>size[pos]) pos=edge[i].to;
- }
- if(pos!=-1) search_(pos,chain);
- for(inti=head[now];i;i=edge[i].next)
- {
- if(edge[i].to==f[now]||edge[i].to==pos)continue;
- search_(edge[i].to,edge[i].to);
- }
- end[now]=cnt;
- }
- voidtree_build(intnow,intl,int r)
- {
- tree[now].l=l,tree[now].r=r;
- tree[now].lit=r-l+1;
- if(l==r)return ;
- tree[now].mid=(l+r)>>1;
- tree_build(now<<1,l,tree[now].mid);
- tree_build(now<<1|1,tree[now].mid+1,r);
- }
- inline voidtree_up(int now)
- {
- tree[now].dis=tree[now<<1].dis+tree[now<<1|1].dis;
- }
- inline voidtree_down(int now)
- {
- if(tree[now].lit==1)return ;
- if(tree[now].flag==1)
- {
- tree[now<<1].dis=0,tree[now<<1|1].dis=0;
- tree[now<<1].flag=tree[now<<1|1].flag=tree[now].flag;
- }
- if(tree[now].flag==2)
- {
- tree[now<<1].dis=tree[now<<1].lit;
- tree[now<<1|1].dis=tree[now<<1|1].lit;
- tree[now<<1].flag=tree[now<<1|1].flag=tree[now].flag;
- }
- tree[now].flag=0;
- }
- voidtree_change(intnow,intl,intr,int type)
- {
- if(tree[now].l==l&&tree[now].r==r)
- {
- tree[now].flag=type;
- if(type==1) tree[now].dis=0;
- elsetree[now].dis=tree[now].lit;
- return ;
- }
- if(tree[now].flag) tree_down(now);
- if(l>tree[now].mid) tree_change(now<<1|1,l,r,type);
- else if(r<=tree[now].mid) tree_change(now<<1,l,r,type);
- else
- {
- tree_change(now<<1,l,tree[now].mid,type);
- tree_change(now<<1|1,tree[now].mid+1,r,type);
- }
- tree_up(now);
- }
- inttree_query(intnow,intl,int r)
- {
- if(tree[now].l==l&&tree[now].r==r)
- {
- return tree[now].dis;
- }
- if(tree[now].flag) tree_down(now);
- tree_up(now);
- if(l>tree[now].mid)returntree_query(now<<1|1,l,r);
- else if(r<=tree[now].mid)returntree_query(now<<1,l,r);
- else returntree_query(now<<1,l,tree[now].mid)+tree_query(now<<1|1,tree[now].mid+1,r);
- }
- inline intsolve(int x)
- {
- intans=0;
- while(belong[x]!=0)
- {
- ans+=(flag[x]-flag[belong[x]]+1)-tree_query(1,flag[belong[x]],flag[x]);
- tree_change(1,flag[belong[x]],flag[x],2);
- x=f[belong[x]];
- }
- ans+=(flag[x]-flag[belong[x]]+1)-tree_query(1,flag[belong[x]],flag[x]);
- tree_change(1,flag[belong[x]],flag[x],2);
- return ans;
- }
- int main()
- {
- read_int(n);
- int to;
- for(inti=1;i)
- {
- read_int(to);
- edge_add(i,to);
- }
- search(0,0),cnt=0,search_(0,0);
- tree_build(1,1,n);
- read_int(m);
- charch[12];
- for(inti=1;i<=m;i++)
- {
- cin>>ch;read_int(to);
- if(ch[0]=='i')
- {
- printf("%d\n",solve(to));
- }
- else
- {
- printf("%d\n",tree_query(1,flag[to],end[to]));
- tree_change(1,flag[to],end[to],1);
- }
- }
- return 0;
- }
来源: