这是代码
```cpp
type
edge=record
d,next:longint;
end;
rec=record
l,r,sum,flag,mid:longint;
end;
var
w,son,top,fa,size,first:array[0..100000]of longint;
a:array[0..100000]of edge;
tree:array[0..500000]of rec;
n,m,i,j,x,tot,sum:longint;
s1,s2:char;
procedure add(x,y:longint);
begin
inc(tot);
a[tot].d:=y;
a[tot].next:=first[x];
first[x]:=tot;
end;
procedure dfs1(x,y:longint);
var
i:longint;
begin
fa[x]:=y; //dep[x]:=deep;
i:=first[x]; size[x]:=1;
while i<>0 do
begin
dfs1(a[i].d,x);
inc(size[x],size[a[i].d]);
if(son[x]=0)or(size[son[x]]<size[a[i].d]) then
son[x]:=a[i].d;
i:=a[i].next;
end;
end;
procedure dfs2(x,t:longint);
var
i:longint;
begin
top[x]:=t; inc(sum);
w[x]:=sum;
if son[x]<>0 then
dfs2(son[x],t);
i:=first[x];
while i<>0 do
begin
if a[i].d<>son[x] then
dfs2(a[i].d,a[i].d);
i:=a[i].next;
end;
end;
procedure build(k,l,r:longint);
begin
tree[k].l:=l;
tree[k].r:=r;
tree[k].flag:=-1;
tree[k].mid:=(l+r)>>1;
if l<>r then
begin
build(k*2,l,(l+r)>>1);
build(k*2+1,(l+r)>>1+1,r);
end;
end;
function change(k,l,r,x:longint):Longint;
begin
if tree[k].flag<>-1 then
begin
if tree[k].flag=0 then
tree[k].sum:=0 else
tree[k].sum:=tree[k].r-tree[k].l+1;
if tree[k].l<>tree[k].r then
begin
tree[k*2].flag:=tree[k].flag;
tree[k*2+1].flag:=tree[k].flag;
end;
tree[k].flag:=-1;
end;
if(tree[k].l=l)and(tree[k].r=r)then
begin
if x=0 then change:=-tree[k].sum else
change:=tree[k].r-tree[k].l+1-tree[k].sum;
tree[k].flag:=x;
exit;
end;
if tree[k].mid>=r then
change:=change(k*2,l,r,x) else
if tree[k].mid<l then
change:=change(k*2+1,l,r,x) else
begin
change:=change(k*2,l,tree[k].mid,x);
change:=change+change(k*2+1,tree[k].mid+1,r,x);
end;
tree[k].sum:=tree[k].sum+change;
end;
procedure solve1(x:longint);
var
i,j:longint;
begin
i:=x; j:=0;
while i<>-1 do
begin
inc(j,change(1,w[top[i]],w[i],1));
i:=fa[top[i]];
end;
writeln(j);
end;
procedure solve2(x:longint);
begin
writeln(-change(1,w[x],w[x]+size[x]-1,0));
end;
begin
readln(n);
for i:=1 to n-1 do
begin
read(x);
add(x,i);
end;
dfs1(0,-1);
dfs2(0,0);
build(1,1,sum);
readln(m);
for i:=1 to m do
begin
read(s1);read(s2);
while s2<>' ' do
read(s2);
readln(x);
if s1='i' then
solve1(x) else
solve2(x);
end;
end.
```
by zmh964685331 @ 2015-07-21 14:13:38
换C++啊，多大点事，真是的
by Claude @ 2015-07-21 16:03:37
同栈溢出。。话说洛谷中Pascal的栈有多大?
by abslime @ 2015-07-27 19:38:51
感觉不科学啊，为何100000层的递归都会挂
by abslime @ 2015-07-30 23:19:03
这好办，改成人工栈就行了，附上AC代码：
```cpp
program zht;
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
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;
end.
```
by zhtjtcz @ 2016-03-03 14:06:49
感觉手工栈写起来不太方便啊
by McGrady @ 2016-12-16 23:17:00
这个数字竟然没人考古
~~我来做考古第一人——~~
by 飞啾6373 @ 2021-10-04 15:54:18
@[飞啾6373](/user/378928) 考古
by _Komorebi_ @ 2023-06-08 19:14:52