```cpp
#include <bits/stdc++.h>
using namespace std;
const int N= 1e5+ 5;
int n, m, vl[N], cnt, a[N], loc[N], siz[N], fa[N], top[N];
vector< int> e[N];
void gc(char chr[])
{
char ch; int res= 0;
while((ch= getchar())< 'a' || ch> 'z');
while(ch>= 'a' && ch<= 'z') chr[res++]= ch, ch= getchar();
return;
}
class segt
{
struct tree
{
int sum, tg;
} t[N<< 2];
void pushup(int u)
{
t[u].sum= t[u<< 1].sum+ t[u<< 1| 1].sum;
}
void pushdown(int u, int len)
{
t[u<< 1].sum= (len- (len>> 1))* (t[u].tg- 1);
t[u<< 1| 1].sum= (len>> 1)* (t[u].tg- 1);
t[u<< 1].tg= t[u].tg;
t[u<< 1| 1].tg= t[u].tg;
t[u].tg= 0;
}
public:
void update(int u, int l, int r, int L, int R, int val)
{
if(l> R || r< L) return;
if(l>= L && r<= R)
{
t[u].sum= (r- l+ 1)* val;
t[u].tg= val+ 1;
return;
}
if(t[u].tg) pushdown(u, r- l+ 1);
int mid= l+ r>> 1;
update(u<< 1, l, mid, L, R, val);
update(u<< 1| 1, mid+ 1, r, L, R, val);
pushup(u);
return;
}
int query(int u, int l, int r, int L, int R)
{
if(l> R || r< L) return 0;
if(l>= L && r<= R) return t[u].sum;
if(t[u].tg) pushdown(u, r- l+ 1);
int mid= l+ r>> 1, res= 0;
res+= query(u<< 1, l, mid, L, R);
res+= query(u<< 1| 1, mid+ 1, r, L, R);
return res;
}
} T;
int tree_ins(int x)
{
int res= 0;
while(top[x]!= 0)
{
res+= loc[top[x]]- loc[x]+ 1- T.query(1, 1, n, loc[top[x]], loc[x]);
T.update(1, 1, n, loc[top[x]], loc[x], 1);
x= fa[top[x]];
}
res+= loc[x]- T.query(1, 1, n, 1, loc[x]);
T.update(1, 1, n, 1, loc[x], 1);
return res;
}
void get_prepared(int u, int f)
{
fa[u]= f, siz[u]= 1;
for(auto v : e[u])
if(v!= f)
get_prepared(v, u), siz[u]+= siz[v];
}
void get_dfs(int u, int f)
{
loc[u]= ++cnt;
int mx= -1, ms= 0;
for(auto v : e[u])
if(v!= f)
if(siz[v]> ms) ms= siz[v], mx= v;
if(mx!= -1) top[mx]= top[u], get_dfs(mx, u);
for(auto v : e[u])
if(v!= f && v!= mx)
top[v]= v, get_dfs(v, u);
}
signed main()
{
scanf("%d", &n);
int v;
for(int i= 1; i< n; i++)
{
scanf("%d", &v);
e[i].push_back(v), e[v].push_back(i);
}
get_prepared(0, -1);
get_dfs(0, -1);
char opt[15]; int x;
scanf("%d", &m);
while(m--)
{
gc(opt); scanf("%d", &x);
if(opt[0]== 'i') printf("%d\n", tree_ins(x));
if(opt[0]== 'u') printf("%d\n", T.query(1, 1, n, loc[x], loc[x]+ siz[x]- 1)), T.update(1, 1, n, loc[x], loc[x]+ siz[x]- 1, 0);
}
return 0;
}
```
by Iggle_Piggle @ 2023-11-23 20:32:43
*所以->所有
by Iggle_Piggle @ 2023-11-23 20:33:10