1. 题目

LUOGU 传送门=￣ω￣=
BZOJ 传送门=￣ω￣=

2. 题解

学 lct 太累娱乐一下
获得了满满的满足感
树链剖分模板题
首先 install 操作就是先查询根节点 (0) 到当前节点的路径，再把这个路径上所有值设为 0
然后 uninstall 操作就是操作子树，子树在线段树上的编号 (以 a 为根的子树) 是 [pos[a],pos[a]+size[a]-1]，直接操作就行了

代码：

#include <bits/stdc++.h>
#define NS (100005)
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,siz[NS],dep[NS],fa[NS],pos[NS],top[NS],tag[NS],cnt;
char opt[15];
struct N{int l,r,d,f;N(){l=r=d=0,f=-1;}}e[NS<<2];
vector<int> g[NS];
void update(int a){e[a].d=e[LS(a)].d+e[RS(a)].d;}
void pdown(int a)
{
    e[LS(a)].d=(e[LS(a)].r-e[LS(a)].l+1)*e[a].f;
    e[RS(a)].d=(e[RS(a)].r-e[RS(a)].l+1)*e[a].f;
    e[LS(a)].f=e[RS(a)].f=e[a].f,e[a].f=-1;
}
void build(int l,int r,int a)
{
    e[a].l=l,e[a].r=r;
    if(l==r){e[a].d=1;return;}
    build(l,(l+r)>>1,LS(a)),build(((l+r)>>1)+1,r,RS(a)),update(a);
}
void change(int l,int r,int k,int a)
{
    if(l<=e[a].l&&e[a].r<=r){e[a].d=(e[a].r-e[a].l+1)*k,e[a].f=k;return;}
    if(e[a].f!=-1)pdown(a);
    if(l<=((e[a].l+e[a].r)>>1))change(l,r,k,LS(a));
    if(r>((e[a].l+e[a].r)>>1))change(l,r,k,RS(a));
    update(a);
}
int query(int l,int r,int a)
{
    if(l<=e[a].l&&e[a].r<=r)return e[a].d;
    if(e[a].f!=-1)pdown(a);
    int tot=0;
    if(l<=((e[a].l+e[a].r)>>1))tot+=query(l,r,LS(a));
    if(r>((e[a].l+e[a].r)>>1))tot+=query(l,r,RS(a));
    return tot;
}
void dfs1(int u)
{
    siz[u]=1,dep[u]=dep[fa[u]]+1;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u])fa[g[u][i]]=u,dfs1(g[u][i]),siz[u]+=siz[g[u][i]];
}
void dfs2(int u)
{
    pos[u]=cnt,tag[cnt]=u,cnt++;
    int nxt=0,maxn=0;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&siz[g[u][i]]>maxn)maxn=siz[g[u][i]],nxt=g[u][i];
    if(!nxt)return;
    top[nxt]=top[u],dfs2(nxt);
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&g[u][i]!=nxt)top[g[u][i]]=g[u][i],dfs2(g[u][i]);
}
void work1(int a)
{
    int tot=0;
    while(a!=-1)
        tot+=query(pos[top[a]],pos[a],1),
        change(pos[top[a]],pos[a],0,1),a=fa[top[a]];
    printf("%d\n",tot);
}
void work2(int a)
{
    printf("%d\n",siz[a]-query(pos[a],pos[a]+siz[a]-1,1));
    change(pos[a],pos[a]+siz[a]-1,1,1);
}
int main()
{
    IN(n);
    for(int i=1,a;i<n;i++)IN(a),g[a].push_back(i);
    dfs1(0),top[0]=0,dfs2(0),build(0,cnt-1,1),fa[0]=-1,IN(m);
    for(int i=1,j;i<=m;i++)
        if(scanf("%s",opt),IN(j),opt[0]=='i')work1(j);else work2(j);
    return 0;
}