显然链剖 然而只询问到根的信息，不用管lca，要好些很多（虽然我没那么写）
对于安装 查询和维护到根路径
对于卸载 查询和维护子树信息
因为链剖本身是用dfs序建的线段树，所以使得查询和修改子树非常方便。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm> using namespace std; const int Maxn=;
int n;
struct Data{
int num[];
Data(int a=,int b=) {num[]=a,num[]=b;}
Data operator + (const Data&rhs) const {
return Data(num[]+rhs.num[],num[]+rhs.num[]);
}
}; struct SegmentTree{
Data da[Maxn*];
int tag[Maxn*];
int lft,rgt,w; void add_tag(int s,int l,int r,int w) {
if(w==-) return;
da[s].num[w]=r-l+;
da[s].num[w^]=;
tag[s]=w;
} void down(int s,int l,int r) {
if(tag[s]==- || l==r) return;
int mid=(l+r)>>;
add_tag(s<<,l,mid,tag[s]);
add_tag(s<<|,mid+,r,tag[s]);
tag[s]=-;
} void change(int s,int l,int r) {
if(lft<=l && r<=rgt) {
add_tag(s,l,r,w);
return;
}
down(s,l,r);
int mid=(l+r)>>;
if(lft<=mid) change(s<<,l,mid);
if(mid<rgt) change(s<<|,mid+,r);
da[s] = da[s<<] + da[s<<|];
}
Data query(int s,int l,int r) {
if(lft<=l&&r<=rgt) return da[s];
down(s,l,r);
int mid=(l+r)>>;
if(rgt<=mid) return query(s<<,l,mid);
if(mid<lft) return query(s<<|,mid+,r);
return query(s<<,l,mid) + query(s<<|,mid+,r);
}
void build(int s,int l,int r) {
if(l==r) {
da[s]=Data(,);
return;
}
int mid=(l+r)>>;
build(s<<,l,mid);
build(s<<|,mid+,r);
da[s]=da[s<<]+da[s<<|];
}
}seg; int sz[Maxn],fa[Maxn],son[Maxn],dep[Maxn]; struct Edge {
int to;
Edge*next;
Edge(int to=,Edge*next=):to(to),next(next) {}
}pool[Maxn*],*pis=pool,*fir[Maxn]; void AddEdge(int from,int to) {
*pis=Edge(to,fir[from]);fir[from]=pis++;
*pis=Edge(from,fir[to]);fir[to]=pis++;
} void dfs(int u) {
sz[u] = ;
son[u] = ;
for(Edge*p=fir[u];p;p=p->next) {
int v=p->to;
if(v==fa[u]) continue;
fa[v]=u;
dep[v]=dep[u]+;
dfs(v);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]]) son[u]=v;
}
} int pos[Maxn],top[Maxn],tm,end[Maxn]; void build(int u,int pre) {
top[u] = pre;
pos[u] = ++tm;
if(son[u]) build(son[u],pre);
for(Edge*p=fir[u];p;p=p->next) {
int v=p->to;
if(v==fa[u] || v==son[u]) continue;
build(v,v);
}
end[u]=tm;
} Data query(int a,int b) {
int ta=top[a],tb=top[b];
Data ret;
for(;ta!=tb;a=fa[ta],ta=top[a]) {
if(dep[ta]<dep[tb]) swap(a,b) ,swap(ta,tb);
seg.lft=pos[ta],seg.rgt=pos[a];
ret=ret+seg.query(,,n);
}
if(dep[a]>dep[b]) swap(a,b);
seg.lft=pos[a],seg.rgt=pos[b];
Data tmp=seg.query(,,n);
return ret+tmp;
} void change(int a,int b,int c) {
int ta=top[a],tb=top[b];
Data ret;
for(;ta!=tb;a=fa[ta],ta=top[a]) {
if(dep[ta]<dep[tb]) swap(a,b) ,swap(ta,tb);
seg.lft=pos[ta],seg.rgt=pos[a];seg.w=c;
seg.change(,,n);
}
if(dep[a]>dep[b]) swap(a,b);
seg.lft=pos[a],seg.rgt=pos[b],seg.w=c;
return seg.change(,,n);
} void init() {
memset(seg.tag,-,sizeof seg.tag);
scanf("%d",&n);
for(int x,i=;i<n;i++) {
scanf("%d",&x);
AddEdge(i+,x+);
}
dfs();
build(,);
seg.build(,,n); // seg.lft=1,seg.rgt=n,seg.w=0;change(1,1,n);
} void work() {
int m,x;
char opt[];
for(scanf("%d",&m);m--;) {
scanf("%s%d",opt,&x);x++;
if(opt[]=='i') {
printf("%d\n",query(x,).num[]);
change(x,,);
}else {
seg.lft=pos[x],seg.rgt=end[x],seg.w=;
printf("%d\n",seg.query(,,n).num[]);
seg.change(,,n);
}
}
} int main() {
freopen("manager.in","r",stdin);
freopen("manager.out","w",stdout); init();
work(); return ;
}