***题目链接戳我***

　　又是在树上瞎搞滴题目....

　　我们如果以安装的软件为1，未安装的软件为0，那么软件改变的数量即树上权值总和的数量，涉及到区间修改，区间查询，考虑树剖

　　分析完毕，似乎没啥好说的了。。。树剖模板题（然鹅我是不会告诉你们我因为把int打成char查了好久好久代码滴...）　　　

　　细节问题：为了便于处理把每个节点编号都加上1，避免一些不必要的错误

　　P.S.打完才发现好像不用区间查询

　　代码：

 1 #include<cstdio>
 2 #include<cctype>
 3 #include<iostream>
 4 using namespace std;
 5 inline int read(){
 6     int ans=0,f=1;char chr=getchar();
 7     while(!isdigit(chr)){if(chr=='-')f=-1;chr=getchar();}
 8     while(isdigit(chr)) {ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
 9     return ans*f;
10 }const int M=200005;int n,m;
11 inline int abs(int x) {if(x<0) return -x;return x;}
12 int head[M],ver[M],nxt[M],tot,fa[M],dep[M],son[M],top[M],idx[M],sz[M],t,sum[M<<2],lz[M<<2];    
13 inline void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
14 void dfs1(int x){
15     dep[x]=dep[fa[x]]+1;sz[x]=1;
16     for(int i=head[x];i;i=nxt[i]){
17         if(ver[i]==fa[x]) continue;
18         fa[ver[i]]=x,dfs1(ver[i]);sz[x]+=sz[ver[i]];
19         if(sz[ver[i]]>sz[son[x]]) son[x]=ver[i];
20     }
21 }void dfs2(int x,int topf){
22     idx[x]=++t;top[x]=topf;
23     if(!son[x]) return;dfs2(son[x],topf);
24     for(int i=head[x];i;i=nxt[i])
25         if(!idx[ver[i]]) dfs2(ver[i],ver[i]);
26 }inline void Push_Up(int i){sum[i]=sum[i<<1]+sum[i<<1|1];}
27  inline void Push_Down(int i,int l,int r){
28      if(lz[i]==0) return;int mid=l+r>>1;
29      if(lz[i]==-1) sum[i<<1]=sum[i<<1|1]=0,lz[i<<1]=lz[i<<1|1]=-1;
30      else sum[i<<1]=mid-l+1,sum[i<<1|1]=r-mid,lz[i<<1]=lz[i<<1|1]=1;
31      lz[i]=0;return;
32 }void Update(int i,int l,int r,int ql,int qr,int x){
33     if(ql<=l&&r<=qr){
34         if(!x)lz[i]=-1,sum[i]=0;//lz==-1-->Update->0  lz==1 --> Update->1
35         else lz[i]=1,sum[i]=r-l+1;
36         return;
37     }int mid=l+r>>1;Push_Down(i,l,r);
38     if(mid>=ql) Update(i<<1,l,mid,ql,qr,x);
39     if(mid<qr)  Update(i<<1|1,mid+1,r,ql,qr,x);
40     Push_Up(i);
41 }void Change(int v,int x,int y){
42     while(top[x]!=top[y]){
43         if(dep[top[x]]<dep[top[y]]) swap(x,y);
44         Update(1,1,n,idx[top[x]],idx[x],v);
45         x=fa[top[x]];
46     }if(dep[x]>dep[y]) swap(x,y);Update(1,1,n,idx[x],idx[y],v);
47 }
48 int main(){
49 //    freopen("rjb.in","r",stdin);
50     n=read();
51     for(int i=2;i<=n;i++){int x=read();++x;add(x,i);add(i,x);}
52     dfs1(1),dfs2(1,1);
53     m=read();char opt[20];int x,bf;
54     while(m--){scanf("%s",opt);x=read();bf=sum[1];++x; 
55         if(opt[0]=='i'){
56             Change(1,x,1);
57             printf("%d\n",abs(sum[1]-bf));
58         }else{
59             Update(1,1,n,idx[x],idx[x]+sz[x]-1,0);
60             printf("%d\n",abs(sum[1]-bf));
61         }
62     }
63     return 0;
64 }