记录编号	219943	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]软件包管理器	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	Pascal	运行时间	8.048 s
提交时间	2016-01-16 21:05:50	内存使用	16.75 MiB

uses math;
type
link=^way;
way=record
  son:longint;
  next:link;            //0 means it's uninstalled,1 means it's installed.
  end;
rec=record
  l,r,v,y,len:longint;
  end;
var
n,q,i,j,x,y,count1,c,ans,l,r:longint;
fa,f,count,hash,edge,lian:array[0..100000]of longint;
w,pro:array[0..100000]of link;
xd:array[0..800000]of rec;
s:string;
a,b:link;

  procedure readl;
  var
  ch:char;
  begin
  s:='';
  repeat
    read(ch);
    if ch<>' ' then s:=s+ch;
    until ch=' ';
  readln(x);x:=hash[x];
  end;

  procedure mtree(x:longint);
  var
  i:link;
  begin
  count[x]:=1;i:=w[x];
  while i<>nil do
    begin
    mtree(i^.son);
    inc(count[x],count[i^.son]);
    i:=i^.next;
    end;
  end;

  procedure process(x:longint);
  var
  i:link;
  begin
  inc(count1);hash[x]:=count1;
  i:=w[x];
  while i<>nil do
    begin
    process(i^.son);i:=i^.next;
    end;
  end;

  procedure exchange;
  var
  i:longint;
  begin
  for i:=0 to n do
  f[hash[i]]:=count[i];
  for i:=0 to n do
  count[i]:=f[i];
  for i:=0 to n do
  f[hash[i]]:=hash[fa[i]];
  for i:=0 to n do
  fa[i]:=f[i];
  end;

  procedure makeedge;
  var
  i,j,count:longint;
  begin
  i:=0;count:=1;edge[0]:=1;lian[1]:=0;
  for j:=1 to n do
  if fa[j]=i then
    begin
    edge[j]:=count;i:=j;
    end
  else
    begin
    inc(count);edge[j]:=count;i:=j;lian[count]:=j;
    end;
  edge[n]:=count;
  end;

  procedure makexd(x:longint);
  var
  m:longint;
  begin
  with xd[x] do
    begin
    len:=xd[x].r-xd[x].l+1;
    if l=r then exit;
    m:=(l+r) div 2;
    xd[x*2].l:=l;xd[x*2].r:=m;
    xd[x*2+1].l:=m+1;xd[x*2+1].r:=r;
    makexd(x*2);makexd(x*2+1);
    end;
  end;

  function qj(a,b,c,d:longint):longint;
  begin
  exit(min(b,d)-max(a,c)+1);
  end;

  function sum(x,a:longint):longint;
  begin
  if (xd[x].l>r)or(xd[x].r<l) then exit(0);
  case xd[x].y of
    1:xd[x].v:=xd[x].len;
    -1:xd[x].v:=0;
    end;
  if xd[x].y<>0 then
    begin
    xd[x*2].y:=xd[x].y;xd[x*2+1].y:=xd[x].y;xd[x].y:=0;
    end;
  if (xd[x].l>=l)and(xd[x].r<=r) then
  case a of
    1:exit(xd[x].len-xd[x].v);
    -1:exit(xd[x].v);
    end;
  sum:=sum(x*2,a)+sum(x*2+1,a);
  end;

  procedure add(x,a:longint);
  var
  i,d:longint;
  bool:boolean;
  begin
  if (xd[x].l>r)or(xd[x].r<l) then exit;
  bool:=false;
  case xd[x].y of
    1:xd[x].v:=xd[x].len;
    -1:xd[x].v:=0;
    end;
  if (xd[x].l>=l)and(xd[x].r<=r) then
    begin
    xd[x].y:=a;
    case a of
      1:d:=xd[x].len-xd[x].v;
      -1:d:=-xd[x].v;
      end;
    i:=x;
    repeat
      inc(xd[i].v,d);i:=i div 2;
      until i=0;
    bool:=true;
    end;
  if xd[x].y<>0 then
    begin
    xd[x*2].y:=xd[x].y;xd[x*2+1].y:=xd[x].y;xd[x].y:=0;
    end;
  if bool then exit;
  add(x*2,a);add(x*2+1,a);
  end;

  procedure install(x:longint);
  var
  i,j:longint;
  begin
  i:=x;
  repeat
    j:=lian[edge[i]];l:=j;r:=i;
    ans:=ans+sum(1,1);add(1,1);
    i:=fa[j];
    until j=0;
  end;

  procedure uninstall(x:longint);
  begin
  l:=x;r:=x+count[x]-1;
  ans:=sum(1,-1);
  add(1,-1);
  end;

begin
assign(input,'manager.in');
reset(input);
assign(output,'manager.out');
rewrite(output);
read(n);
dec(n);
for i:=1 to n do
read(fa[i]);

for i:=0 to n do
  begin
  new(w[i]);pro[i]:=w[i];w[i]^.next:=nil;
  end;
for i:=1 to n do
  begin
  new(pro[fa[i]]^.next);
  pro[fa[i]]:=pro[fa[i]]^.next;
  pro[fa[i]]^.son:=i;
  pro[fa[i]]^.next:=nil;
  end;
for i:=0 to n do w[i]:=w[i]^.next;

mtree(0);

for i:=0 to n do
  begin
  b:=w[i];
  if b=nil then continue;
  repeat
    b:=b^.next;
    if b=nil then break;
    if count[w[i]^.son]<count[b^.son] then
      begin
      y:=b^.son;b^.son:=w[i]^.son;w[i]^.son:=y;
      end;
    until 1=2;
  end;

count1:=-1;
process(0);
exchange;
makeedge;
xd[1].l:=0;xd[1].r:=n;
makexd(1);

readln(q);
for q:=1 to q do
  begin
  readl;
  ans:=0;
  case s[1] of
    'i':install(x);
    'u':uninstall(x);
    end;
  writeln(ans);
  end;
close(input);
close(output);
end.