[NOI2015] 软件包管理器

题目背景

Linux 用户和 OSX 用户一定对软件包管理器不会陌生。

通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。

Debian/Ubuntu 使用的 apt-get，Fedora/CentOS 使用的 yum，以及 OSX 下可用的 homebrew 都是优秀的软件包管理器。

题目描述

你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。

如果软件包 $a$ 依赖软件包 $b$，那么安装软件包 $a$ 以前，必须先安装软件包 $b$。

同时，如果想要卸载软件包 $b$，则必须卸载软件包 $a$。

现在你已经获得了所有的软件包之间的依赖关系。

而且，由于你之前的工作，除 $0$ 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 $0$ 号软件包不依赖任何一个软件包。

且依赖关系不存在环（即不会存在 $m$ 个软件包 $a_1,a_2,\dots ,a_m$，对于 $i<m$，$a_i$ 依赖 $a_{i+1}$，而 $a_m$ 依赖 $a_1$ 的情况）。

现在你要为你的软件包管理器写一个依赖解决程序。

根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。

注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 $0$。

输入格式

第一行一个正整数 $n$，表示软件包个数，从 $0$ 开始编号。
第二行有 $n-1$ 个整数，第 $i$ 个表示 $i$ 号软件包依赖的软件包编号。
然后一行一个正整数 $q$，表示操作个数，格式如下：

• install x 表示安装 $x$ 号软件包
• uninstall x 表示卸载 $x$ 号软件包

一开始所有软件包都是未安装的。

对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。

输出格式

输出 $q$ 行，每行一个整数，表示每次询问的答案。

样例 #1

样例输入 #1

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

样例输出 #1

3
1
3
2
3

样例 #2

样例输入 #2

10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

样例输出 #2

1
3
2
1
3
1
1
1
0
1

提示

一开始所有软件包都处于未安装状态。

安装 $5$ 号软件包，需要安装 $0,1,5$ 三个软件包。

之后安装 $6$ 号软件包，只需要安装 $6$ 号软件包。此时安装了 $0,1,5,6$ 四个软件包。

卸载 $1$ 号软件包需要卸载 $1,5,6$ 三个软件包。此时只有 $0$ 号软件包还处于安装状态。

之后安装 $4$ 号软件包，需要安装 $1,4$ 两个软件包。此时 $0,1,4$ 处在安装状态。最后，卸载 $0$ 号软件包会卸载所有的软件包。

//每次安装软件，就把根节点到x软件路径上的值全部变为1；
//同理，每次卸载软件，就把x以及它的子树的值变为0；
//然后利用区间加减获取改变数量
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int head[N],cnt;
int fa[N],size[N],deep[N],son[N],top[N],dfsxu[N],id[N],k;
//fa[i] 节点i的父节点 size[i] 以i为根的子树总节点数
//deep[i] 节点i的深度 son[i] 节点i的重儿子
//top[i] 节点i所在的重链的最顶上元素
//dfsxu 各点初始值 id 时间戳
//dfs序是能够反映树上的点连续的信息的，链就是dfs序
int n,v[N],m,r,ss[N];
struct stu{
    
    int l,r,sum,lz;
}tree[N*4];
struct stuu{
    
	int to,nt;
}ed[N*2];
void add(int u,int v){
    //链式前向星加边
	ed[cnt]=stuu{
    v,head[u]};
	head[u]=cnt++;
}
void dfs1(int u,int f){
    //u为当前节点,f为当前节点的父节点；初始化1
    fa[u]=f;//u节点的父节点是f
    deep[u]=deep[f]+1;//深度+1
    size[u]=1;
    int maxsize=-1;//判断是不是重儿子的临时变量
    for(int i=head[u];i!=-1;i=ed[i].nt){
    //遍历所有儿子，不断更新同时找到重儿子
		int v=ed[i].to;
        if(v==f) continue;//是父亲肯定直接跳过
        dfs1(v,u);//深度遍历,当前节点变为父节点，找到的儿子变为当前节点继续遍历下去
        size[u]+=size[v];//遍历完成后，让当前节点的大小加上儿子的大小
        if(size[v]>maxsize){
    //如果儿子的大小大于临时变量
            maxsize=size[v];//就赋给临时变量
            son[u]=v;//更改当前节点的重儿子
        }
    }
}
void dfs2(int u,int t){
    //初始化2
    id[u]=++k;//每到了一个节点赋时间戳
    top[u]=t;//节点u所在重链的顶端是t
    dfsxu[k]=u;//存好dfs序
    if(!son[u]) return;//没有重儿子就没儿子了直接返回
    dfs2(son[u],t);//继续往重儿子走
    for(int i=head[u];i!=-1;i=ed[i].nt){
    
        int v =ed[i].to;
        if(v==fa[u]||v==son[u]) continue;//如果是父节点或重儿子直接跳过
        dfs2(v,v);//一些重链从轻儿子开始往下有,顶部是轻儿子
    }
}
void pushup(int u){
    //向上更新
    tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;//左右两子段的区间和相加反馈给顶部
}
void pushdown(int u){
    //向下更新，将lazy标向下推
    if(tree[u].lz!=-1){
    
        tree[u<<1].sum=tree[u].lz*(tree[u<<1].r-tree[u<<1].l+1);
        tree[u<<1|1].sum=tree[u].lz*(tree[u<<1|1].r-tree[u<<1|1].l+1);
        tree[u<<1].lz=tree[u].lz;
        tree[u<<1|1].lz=tree[u].lz;
        tree[u].lz=-1;
    }
}
void build(int l,int r,int u){
    //建树
    tree[u].l=l,tree[u].r=r,tree[u].lz=-1;
	if(l==r){
    //到达叶子结点，返回
		return ;
	}//否则这个结点代表的不止一个点，它还有两个儿子
	int mid=(l+r)>>1;
	build(l,mid,u<<1);//递归左子树
	build(mid+1,r,u<<1|1);//递归右子树
	pushup(u);//更新
}
void update(int l,int r,int u,int b){
    
    if(l<=tree[u].l&&tree[u].r<=r){
    //作为子区间被包含，则进行整体修改，不继续深入
        tree[u].sum=b*(tree[u].r-tree[u].l+1);
        tree[u].lz=b;
        return ;
    }//否则处于交错，则需要继续深入更底层子区间
    pushdown(u);//向下更新
    int mid=(tree[u].l+tree[u].r)>>1;
	if(l<=mid) update(l,r,u<<1,b);//递归左子树
	if(r>=mid+1) update(l,r,u<<1|1,b);//递归右子树
	pushup(u);//更新
}
void updatecc(int a,int b,int c){
    
    while(top[a]!=top[b]){
    //找LCA：当x,y不在同一条重链，比较x,y所在重链链首的深度大小
        if(deep[top[a]]<deep[top[b]]) swap(a,b);//确保较深
        update(id[top[a]],id[a],1,c);//通过爬lca时每次跳链头来区间修改或查询
        a=fa[top[a]];//较深的那个沿着重链跳到链首的父亲处
    }
    if(deep[a]>deep[b]) swap(a,b);//在一条重链上就能直接操作了
    update(id[a],id[b],1,c);
}
int main(){
    
    int kk;
    memset(head,-1,sizeof(head));
    cin>>n;
    for(int i=2;i<=n;i++){
    
        scanf("%d",&kk);
        kk++;
        add(kk,i);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,n,1);
    scanf("%d",&m);
    while(m--){
    
        int s1=tree[1].sum,s2;
        string p;
        cin>>p>>kk;
        kk++;
        if(p[0]=='i'){
    
            updatecc(1,kk,1);
            s2=tree[1].sum;
            printf("%d\n",abs(s1-s2));
        }
        else if(p[0]=='u'){
    
            update(id[kk],id[kk]+size[kk]-1,1,0);
            s2=tree[1].sum;
            printf("%d\n",abs(s1-s2));
        }
    }
}