Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的yum，以及OSX下可用的homebrew都是优秀的软件包管理器。
你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包A依赖软件包B，那么安装软件包A以前，必须先安装软件包B。同时，如果想要卸载软件包B，则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除0号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环（若有m(m≥2)个软件包A1,A2,A3,…,Am，其中A1依赖A2，A2依赖A3，A3依赖A4，……，Am−1依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。
输入文件的第1行包含1个正整数n，表示软件包的总数。软件包从0开始编号。
随后一行包含n−1个整数，相邻整数之间用单个空格隔开，分别表示1,2,3,…,n−2,n−1号软件包依赖的软件包的编号。
接下来一行包含1个正整数q，表示询问的总数。
之后q行，每行1个询问。询问分为两种：
installx：表示安装软件包x
uninstallx：表示卸载软件包x
你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。
输出文件包括q行。
输出文件的第i行输出1个整数，为第i步操作中改变安装状态的软件包数。
1 #pragma GCC optimize(2)
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #define lll spc<<1
6 #define rrr spc<<1|1
7 inline int read()
8 {
9 int l=1;
10 int ret=0;
11 char ch=getchar();
12 while(ch<‘0‘||ch>‘9‘)
13 {
14 if(ch==‘-‘)
15 l=-l;
16 ch=getchar();
17 }
18 while(ch<=‘9‘&&ch>=‘0‘)
19 {
20 ret=ret*10+ch-‘0‘;
21 ch=getchar();
22 }
23 return ret*l;
24 }
25 struct trnt{
26 int val;
27 int len;
28 int lzt;
29 bool chg;
30 }tr[1000000];
31 struct pnt{
32 int hd;
33 int fa;
34 int dp;
35 int tp;
36 int ind;
37 int mxs;
38 int wgt;
39 }p[1000000];
40 struct ent{
41 int twd;
42 int lst;
43 }e[1000000];
44 int cnt;
45 int n,m;
46 int dfn;
47 char cmd[100];
48 void ade(int f,int t)
49 {
50 cnt++;
51 e[cnt].twd=t;
52 e[cnt].lst=p[f].hd;
53 p[f].hd=cnt;
54 }
55 void pushup(int spc)
56 {
57 tr[spc].val=tr[lll].val+tr[rrr].val;
58 tr[spc].len=tr[lll].len+tr[rrr].len;
59 return ;
60 }
61 void Add(int spc,int x)
62 {
63 tr[spc].val=tr[spc].len*x;
64 tr[spc].lzt=x;
65 tr[spc].chg=1;
66 return ;
67 }
68 void pushdown(int spc)
69 {
70 if(tr[spc].chg)
71 {
72 Add(lll,tr[spc].lzt);
73 Add(rrr,tr[spc].lzt);
74 tr[spc].chg=0;
75 }
76 return ;
77 }
78 void build(int l,int r,int spc)
79 {
80 if(l==r)
81 {
82 tr[spc].len=1;
83 return ;
84 }
85 int mid=(l+r)>>1;
86 build(l,mid,lll);
87 build(mid+1,r,rrr);
88 pushup(spc);
89 return ;
90 }
91 void update(int l,int r,int ll,int rr,int spc,int v)
92 {
93 if(l>rr||ll>r)
94 return ;
95 if(ll<=l&&r<=rr)
96 {
97 Add(spc,v);
98 return ;
99 }
100 pushdown(spc);
101 int mid=(l+r)>>1;
102 update(l,mid,ll,rr,lll,v);
103 update(mid+1,r,ll,rr,rrr,v);
104 pushup(spc);
105 return ;
106 }
107 int query(int l,int r,int ll,int rr,int spc)
108 {
109 if(ll>r||l>rr)
110 return 0;
111 if(ll<=l&&r<=rr)
112 return tr[spc].val;
113 pushdown(spc);
114 int mid=(l+r)>>1;
115 return query(l,mid,ll,rr,lll)+query(mid+1,r,ll,rr,rrr);
116 }
117 void Basic_dfs(int x,int f)
118 {
119 p[x].fa=f;
120 p[x].dp=p[f].dp+1;
121 p[x].wgt=1;
122 int maxs=-1;
123 for(int i=p[x].hd;i;i=e[i].lst)
124 {
125 int to=e[i].twd;
126 if(to==f)
127 continue;
128 Basic_dfs(to,x);
129 p[x].wgt+=p[to].wgt;
130 if(maxs<p[to].wgt)
131 {
132 maxs=p[to].wgt;
133 p[x].mxs=to;
134 }
135 }
136 return ;
137 }
138 void Build_dfs(int x,int top)
139 {
140 if(!x)
141 return ;
142 p[x].ind=++dfn;
143 p[x].tp=top;
144 Build_dfs(p[x].mxs,top);
145 for(int i=p[x].hd;i;i=e[i].lst)
146 {
147 int to=e[i].twd;
148 if(p[to].ind)
149 continue;
150 Build_dfs(to,to);
151 }
152 }
153 int Install(int x)
154 {
155 int ans=0;
156 while(p[x].tp!=1)
157 {
158 ans+=p[x].dp-p[p[x].tp].dp-query(1,dfn,p[p[x].tp].ind,p[x].ind,1)+1;
159 update(1,dfn,p[p[x].tp].ind,p[x].ind,1,1);
160 x=p[p[x].tp].fa;
161 }
162 ans+=p[x].dp-query(1,dfn,p[1].ind,p[x].ind,1);
163 update(1,dfn,p[1].ind,p[x].ind,1,1);
164 return ans;
165 }
166 int Uninstall(int x)
167 {
168 int ans=query(1,dfn,p[x].ind,p[x].ind+p[x].wgt-1,1);
169 update(1,dfn,p[x].ind,p[x].ind+p[x].wgt-1,1,0);
170 return ans;
171 }
172 int main()
173 {
174 n=read();
175 for(int i=2;i<=n;i++)
176 {
177 int x=read();
178 x++;
179 ade(x,i);
180 ade(i,x);
181 }
182 dfn=0;
183 Basic_dfs(1,1);
184 Build_dfs(1,1);
185 build(1,dfn,1);
186 m=read();
187 while(m--)
188 {
189 scanf("%s",cmd+1);
190 int x=read();
191 x++;
192 if(cmd[1]==‘i‘)
193 printf("%d\n",Install(x));
194 else
195 printf("%d\n",Uninstall(x));
196 }
197 return 0;
198 }
