[NOI2015] Package manager

Background

Linux Users and OSX Users must be familiar with the package manager .

Through the package manager , You can install a package with a single command , Then the package manager will help you download packages from the source , Automatically resolve all dependencies at the same time （ That is, download and install other software packages that the installation of this software package depends on ）, Complete all configuration .

Debian/Ubuntu The use of apt-get,Fedora/CentOS The use of yum, as well as OSX The next available homebrew Are excellent package managers .

Title Description

You decide to design your own package manager . inevitably , You have to solve the dependency problem between software packages .

If the package $a$ Dependent packages $b$, Then install the package $a$ before , You must first install the package $b$.

meanwhile , If you want to uninstall the package $b$, You must uninstall the package $a$.

Now you have all the dependencies between packages .

and , Because of your previous work , except $0$ Outside package No , Packages in your manager will depend on one and only one package , and $0$ Package No. 1 does not depend on any package .

And there is no ring in the dependency （ That is, there will be no $m$ Software package $a_1,a_2,\dots ,a_m$, about $i<m$,$a_i$ rely on $a_{i+1}$, and $a_m$ rely on $a_1$ The situation of ）.

Now you have to write a dependency resolver for your package manager .

Based on feedback , Users want to install and uninstall a package , Quickly know how many packages the installation state will actually be changed by this operation （ That is, how many uninstalled packages will be installed during the installation operation , Or how many installed packages will be uninstalled ）, Your task is to realize this part .

Be careful , Install an installed package , Or uninstall an uninstalled package , Will not change the installation status of any software package , In this case , The number of packages changing the installation state is $0$.

Input format

First line a positive integer $n$, Indicates the number of software packages , from $0$ Numbered starting .
The second line has $n-1$ It's an integer , The first $i$ A means $i$ Package number on which package number depends .
Then a positive integer on each line $q$, Represents the number of operations , The format is as follows ：

• install x Said the installation $x$ Software package No
• uninstall x Means uninstall $x$ Software package No

At first, all software packages were not installed .

For each operation , You need to output how many packages' installation status will be changed by this operation , Then apply this operation （ That is, change the installation state you maintain ）.

Output format

Output $q$ That's ok , One integer per row , Indicates the answer to each inquiry .

Examples #1

The sample input #1

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

Sample output #1

3
1
3
2
3

Examples #2

The sample input #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

Sample output #2

1
3
2
1
3
1
1
1
0
1

Tips

At first, all software packages are not installed .

install $5$ Software package No , Need to install $0,1,5$ Three packages .

After the installation $6$ Software package No , Just install $6$ Software package No . At this time $0,1,5,6$ Four packages .

uninstall $1$ Package No. needs to be uninstalled $1,5,6$ Three packages . At this time only $0$ Package is still installed .

After the installation $4$ Software package No , Need to install $1,4$ Two packages . here $0,1,4$ In installation state . Last , uninstall $0$ Package No. 1 will uninstall all packages .

// Every time the software is installed , Just connect the root node to x All the values on the software path become 1;
// Empathy , Every time you uninstall the software , Just put x And the value of its subtree becomes 0;
// Then use interval addition and subtraction to obtain the change quantity 
#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]  node i Parent node  size[i]  With i Is the total number of nodes in the subtree of the root 
//deep[i]  node i The depth of the  son[i]  node i My dear son 
//top[i]  node i The top element of the heavy chain 
//dfsxu  Initial value of each point  id  Time stamp 
//dfs Order can reflect the continuous information of points on the tree , The chain is dfs order 
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){
    // Chain forward star edge 
	ed[cnt]=stuu{
    v,head[u]};
	head[u]=cnt++;
}
void dfs1(int u,int f){
    //u Is the current node ,f Is the parent node of the current node ; initialization 1
    fa[u]=f;//u The parent of the node is f
    deep[u]=deep[f]+1;// depth +1
    size[u]=1;
    int maxsize=-1;// It is a temporary variable to judge whether it is a heavy son 
    for(int i=head[u];i!=-1;i=ed[i].nt){
    // Traverse all the sons , Keep updating and find your son 
		int v=ed[i].to;
        if(v==f) continue;// My father must have skipped it directly 
        dfs1(v,u);// Depth traversal , The current node becomes the parent node , The found son becomes the current node and continues to traverse 
        size[u]+=size[v];// After traversal , Let the size of the current node plus the size of the son 
        if(size[v]>maxsize){
    // If the size of the son is larger than the temporary variable 
            maxsize=size[v];// Just assign it to a temporary variable 
            son[u]=v;// Change the heavy son of the current node 
        }
    }
}
void dfs2(int u,int t){
    // initialization 2
    id[u]=++k;// Each node is timestamped 
    top[u]=t;// node u The top of the heavy chain is t
    dfsxu[k]=u;// Save dfs order 
    if(!son[u]) return;// If there is no heavy son, there will be no son. Go back directly 
    dfs2(son[u],t);// Continue to walk towards your son 
    for(int i=head[u];i!=-1;i=ed[i].nt){
    
        int v =ed[i].to;
        if(v==fa[u]||v==son[u]) continue;// If it is a parent node or a duplicate son, skip directly 
        dfs2(v,v);// Some heavy chains start with light sons and go down , The top is light son 
    }
}
void pushup(int u){
    // Update up 
    tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;// The interval sum of the left and right sub segments is fed back to the top 
}
void pushdown(int u){
    // Update down , take lazy Mark push down 
    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){
    // Build up trees 
    tree[u].l=l,tree[u].r=r,tree[u].lz=-1;
	if(l==r){
    // Reach the leaf node , return 
		return ;
	}// Otherwise, this node represents more than one point , It also has two sons 
	int mid=(l+r)>>1;
	build(l,mid,u<<1);// Recursive left subtree 
	build(mid+1,r,u<<1|1);// Recursive right subtree 
	pushup(u);// to update 
}
void update(int l,int r,int u,int b){
    
    if(l<=tree[u].l&&tree[u].r<=r){
    // Included as a subinterval , Then make an overall modification , Don't go further 
        tree[u].sum=b*(tree[u].r-tree[u].l+1);
        tree[u].lz=b;
        return ;
    }// Otherwise, it is staggered , You need to continue to go deeper into the lower sub interval 
    pushdown(u);// Update down 
    int mid=(tree[u].l+tree[u].r)>>1;
	if(l<=mid) update(l,r,u<<1,b);// Recursive left subtree 
	if(r>=mid+1) update(l,r,u<<1|1,b);// Recursive right subtree 
	pushup(u);// to update 
}
void updatecc(int a,int b,int c){
    
    while(top[a]!=top[b]){
    // look for LCA： When x,y Not in the same heavy chain , Compare x,y The depth of the head of the heavy chain 
        if(deep[top[a]]<deep[top[b]]) swap(a,b);// Ensure deeper 
        update(id[top[a]],id[a],1,c);// By climbing lca Every time you jump the chain head to modify or query the interval 
        a=fa[top[a]];// The deeper one jumps along the heavy chain to the father at the head of the chain 
    }
    if(deep[a]>deep[b]) swap(a,b);// It can be operated directly on a heavy chain 
    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));
        }
    }
}