NOI2015 軟件包管理器

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<bitset>
#define ll long long
#define debug(x) cout<<#x<<"  "<<x<<endl;
#define db(x,y)cout<<#x<<" "<<#y<<" "<<x<<" "<<y<<endl;
using namespace std;
inline void rd(int &res){
    res=0;char c;
    while(c=getchar(),c<48);
    do res=(res<<1)+(res<<3)+(c^48);
    while(c=getchar(),c>=48);
}
inline void print(int x){
    if(!x)return ;
    print(x/10);
    putchar((x%10)^48);
}
inline void sc(int x){
    if(x<0){x=-x;putchar('-');}
    print(x);
    if(!x)putchar('0');
    putchar('\n');
}
inline void Max(int &x,int y){if(x<y)x=y;}
inline void Min(int &x,int y){if(x>y)x=y;}
const int M=1e5+5;
int res=0,n,m,sz[M],w[M],tot=0,fa[M],top[M],son[M],head[M],ec=2,to[M],nxt[M];
int dep[M],L[M],R[M];
struct Seg{
    int t[M<<2],f[M<<2];
    void down(int l,int mid,int r,int p){
        if(f[p]==-1)return;
        t[p<<1]=f[p]*(mid-l+1);
        t[p<<1|1]=f[p]*(r-mid);
        f[p<<1]=f[p<<1|1]=f[p];
        f[p]=-1;
    }
    void build(int l,int r,int p){
        f[p]=-1;
        if(l==r)return;
        int mid=l+r>>1;
        build(l,mid,p<<1),build(mid+1,r,p<<1|1);
    }
    void upd(int L,int R,int l,int r,int v,int p){
        if(L==l&&R==r){
            res+=t[p];        
            t[p]=v*(r-l+1);
            f[p]=v;
            return;
        }
        int mid=L+R>>1;
        down(L,mid,R,p);
        if(r<=mid)upd(L,mid,l,r,v,p<<1);
        else if(l>mid)upd(mid+1,R,l,r,v,p<<1|1);
        else upd(L,mid,l,mid,v,p<<1),upd(mid+1,R,mid+1,r,v,p<<1|1);
        t[p]=t[p<<1]+t[p<<1|1];
    }
}T;
void ins(int a,int b){
    to[ec]=b;nxt[ec]=head[a];head[a]=ec++;
}
void dfs(int x){
    sz[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        dep[y]=dep[x]+1;
        dfs(y);
        sz[x]+=sz[y];
        if(!son[x]||sz[y]>sz[son[x]])son[x]=y;//得到大兒子 
    }
}
void build(int x,int tp){
    top[x]=tp;
    L[x]=w[x]=++tot;
    if(son[x])build(son[x],tp);
    for(int i=head[x];i;i=nxt[i]){
        if(to[i]!=son[x])build(to[i],to[i]);
    }
    R[x]=tot;
}
int add_anc(int a){//得到a的祖先的路徑 
    int sum=dep[a];
    res=0;
    while(~a){//求出沒有裝的個數 并且把每個點都裝上 
        T.upd(1,n,w[top[a]],w[a],1,1);//求出已經有的點的個
        a=fa[top[a]];
    }
//    printf("%d %d\n",sum,res);
    return sum-res;
}
int del_son(int a){//刪除自己的所有兒子 
    res=0;
    T.upd(1,n,L[a],R[a],0,1);
    return res; 
}
int main(){

    rd(n);fa[0]=-1;
    char s[20];int i,j,a;
    for(i=1;i<n;i++){
        rd(fa[i]);
        ins(fa[i],i);
    }
    dep[0]=1;
    dfs(0);
    build(0,0);
    rd(m);
    T.build(1,n,1);
    while(m--){
        scanf("%s",s);rd(a);
        if(s[0]=='i'){ 
            sc(add_anc(a));
        }
        else{
            sc(del_son(a));
        }
    }
    return 0;
}