记录编号	232906	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]软件包管理器	最终得分	100
用户昵称	甘罗	是否通过	通过
代码语言	Pascal	运行时间	9.970 s
提交时间	2016-03-03 13:57:36	内存使用	14.90 MiB

program zht;
uses sysutils;
type marvolo=record
     l:longint;
     r:longint;
     la:longint;
     d:longint;
     end;
var
i,j,n,m,h,q,x,tot,p:longint;
time:real;
z,zz:char;
t:array[0..110000,1..3] of longint;
a,b,a2,b2,f,s,son,w,top,right:array[0..110000] of longint;
z1,z2:array[0..200000] of longint;
tree:array[0..500000] of marvolo;

procedure gb(low,high:longint);
var
q,w,e,mid,k:longint;
begin
if low=high then exit;
mid:=(low+high) div 2;
gb(low,mid);
gb(mid+1,high);
q:=low;
w:=mid+1;
e:=low;
while (q<=mid) and (w<=high) do
if a[q]<a[w] then
 begin
 a2[e]:=a[q];
 b2[e]:=b[q];
 inc(e);
 inc(q);
 end else
  begin
  a2[e]:=a[w];
  b2[e]:=b[w];
  inc(e);
  inc(w);
  end;
if q<=mid then
 while q<=mid do
 begin
 a2[e]:=a[q];
 b2[e]:=b[q];
 inc(e);
 inc(q);
 end else
 while w<=high do
 begin
 a2[e]:=a[w];
 b2[e]:=b[w];
 inc(e);
 inc(w);
 end;
for k:=low to high do
begin
a[k]:=a2[k];
b[k]:=b2[k];
end;
end;

procedure bfs1;
var
i:longint;
begin
i:=0;
q:=a[1];
t[a[1],1]:=1;
for i:=2 to n do
if a[i]<>q then begin t[q,2]:=i-1; q:=a[i]; t[q,1]:=i; end;
t[q,2]:=n;
for i:=1 to n do
if t[a[i],1]<>0 then t[a[i],3]:=t[a[i],2]-t[a[i],1]+1;
for i:=1 to n do
s[i]:=1;
h:=1;
z1[1]:=1;
z2[1]:=t[1,3];
while h<>0 do
begin
if z2[h]=0 then begin
 inc(s[z1[h-1]],s[z1[h]]);
 z2[h]:=0;
 z1[h]:=0;
 dec(h);
 continue;
 end;
inc(h);
z1[h]:=b[t[z1[h-1],1]+t[z1[h-1],3]-z2[h-1]];
z2[h]:=t[z1[h],3];
dec(z2[h-1]);
end;
end;

procedure chuli1;
var
i,j,k,q,wz:longint;
begin
i:=0; j:=0; k:=0; q:=0; wz:=0;
for i:=1 to n do
 begin
 k:=0; q:=0; wz:=0;
 for j:=t[i,1] to t[i,2] do
  if j=0 then break else
     if s[b[j]]>q then begin
     q:=s[b[j]]; k:=b[j]; wz:=j;
     end;
 son[i]:=k;
 if wz<>1 then begin b[wz]:=b[t[i,1]]; b[t[i,1]]:=k; end;
 end;
end;

procedure bfs2;
begin
h:=1;
tot:=0;
fillchar(z1,sizeof(z1),0);
fillchar(z2,sizeof(z2),0);
z1[1]:=1;
z2[1]:=t[1,3];
top[1]:=1;
while h<>0 do
begin
if z2[h]=0 then begin
 right[z1[h]]:=tot+1;
 z1[h]:=0;
 z2[h]:=0;
 dec(h);
 continue;
 end;
if son[z1[h]]<>0 then begin top[son[z1[h]]]:=top[z1[h]];
 for j:=t[z1[h],1]+1 to t[z1[h],2] do
 top[b[j]]:=b[j];
 end;
inc(h);
z1[h]:=b[t[z1[h-1],1]+t[z1[h-1],3]-z2[h-1]];
z2[h]:=t[z1[h],3];
w[z1[h]]:=tot+1;
inc(tot);
dec(z2[h-1]);
end;
end;

procedure maketree(x,low,high:longint);
var
mid:longint;
begin
mid:=0;
tree[x].l:=low;
tree[x].r:=high;

tree[x].la:=-1;

if low=high then exit;

mid:=(low+high) div 2;
maketree(x*2,low,mid);
maketree(x*2+1,mid+1,high)
end;

procedure sum(bh,yc:longint);
begin
tree[bh].d:=(tree[bh].r-tree[bh].l+1)*yc;
tree[bh].la:=-1;
if tree[bh].l=tree[bh].r then exit;
tree[bh*2].la:=yc;
tree[bh*2+1].la:=yc;
end;

procedure add(x,low,high,bj:longint);
var
mid:longint;
begin
mid:=0;
mid:=(tree[x].l+tree[x].r) div 2;
if tree[x].la<>-1 then sum(x,tree[x].la);

if tree[x].l=tree[x].r then begin tree[x].d:=bj; exit; end;

if (tree[x].l=low) and (tree[x].r=high) then begin
   tree[x].d:=(tree[x].r-tree[x].l+1)*bj;
   tree[x*2].la:=bj; tree[x*2+1].la:=bj;
   exit;
   end;

if low>mid then add(x*2+1,low,high,bj)
else if high<=mid then add(x*2,low,high,bj)
else begin
     add(x*2,low,mid,bj);
     add(x*2+1,mid+1,high,bj);
     end;

if tree[x*2].la<>-1 then sum(x*2,tree[x*2].la);
if tree[x*2+1].la<>-1 then sum(x*2+1,tree[x*2+1].la);
tree[x].d:=tree[x*2].d+tree[x*2+1].d;

end;

procedure install(x:longint);
var
zc:longint;
begin
zc:=0;
zc:=tree[1].d;

while top[x]<>1 do
begin
add(1,w[top[x]]+1,w[x]+1,1);
x:=f[top[x]];
end;

add(1,w[top[x]]+1,w[x]+1,1);
writeln(tree[1].d-zc);
end;

procedure uninstall(bh:longint);
var
zc:longint;
begin
zc:=0;
zc:=tree[1].d;
add(1,w[bh]+1,right[bh],0);
writeln(zc-tree[1].d);
end;

begin
assign(input,'manager.in');
assign(output,'manager.out');
reset(input);
rewrite(output);

time:=now;

readln(n);

for i:=1 to n-1 do
begin
read(x);
inc(a[0]);
a[a[0]]:=x+1;
b[a[0]]:=i+1;
f[i+1]:=x+1;
end;
f[1]:=1;

gb(1,n-1);

bfs1;
chuli1;
bfs2;
maketree(1,1,n);

q:=0;
readln(q);

for i:=1 to q do
begin
read(z);
zz:=z;
while zz<>' ' do
read(zz);

readln(p);
if z='i' then install(p+1) else uninstall(p+1);
end;
close(input);
close(output);
end.