Lvat_s Blog

树链剖分直接上

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
int dep[100005],top[100005],id[100005],pre[100005],n,q,en,h[100005],fa[100005],son[100005],siz[100005],sn;
 
struct Edge{
int b,next;
}e[100005];
 
void AddEdge(int sa,int sb){
if(sa==sb)return;
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
struct SegTree{
int tag,sum,l,r,rem;
}tree[400005];
 
void Pushdown(int rt){
if(tree[rt].rem){
    tree[rt*2].tag=0;
    tree[rt*2+1].tag=0;
    tree[rt*2].sum=0;
    tree[rt*2+1].sum=0;
    tree[rt].tag=0;
    tree[rt*2].rem=1;
    tree[rt*2+1].rem=1;
    tree[rt].rem=0;
}
if(tree[rt].tag){
    tree[rt*2].tag=1;
    tree[rt*2+1].tag=1;
    tree[rt*2].rem=0;
    tree[rt*2+1].rem=0;
    tree[rt*2].sum=tree[rt*2].r-tree[rt*2].l+1;
    tree[rt*2+1].sum=tree[rt*2+1].r-tree[rt*2+1].l+1;
    tree[rt].tag=0;
}
}
 
void Pushup(int rt){
tree[rt].sum=tree[rt*2].sum+tree[rt*2+1].sum;
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
if(l==r){
    tree[rt].rem=tree[rt].tag=tree[rt].sum=0;
    return;
}
int mid=l+r>>1;
Build(rt*2,l,mid);
Build(rt*2+1,mid+1,r);
tree[rt].rem=tree[rt].tag=tree[rt].sum=0;
}
 
void Add(int rt,int l,int r){
if(tree[rt].l>=l && tree[rt].r<=r){
    tree[rt].tag=1;
    tree[rt].rem=0;
    tree[rt].sum=tree[rt].r-tree[rt].l+1;
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Add(rt*2,l,r);
if(r>mid)Add(rt*2+1,l,r);
Pushup(rt);
}
 
void Del(int rt,int l,int r){
if(tree[rt].l>=l && tree[rt].r<=r){
    tree[rt].rem=1;
    tree[rt].tag=0;
    tree[rt].sum=0;
    return;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Del(rt*2,l,r);
if(r>mid)Del(rt*2+1,l,r);
Pushup(rt);
}
 
int Sum(int rt,int l,int r){
if(tree[rt].l>=l && tree[rt].r<=r){
    return tree[rt].sum;
}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1,ans=0;
if(l<=mid)ans+=Sum(rt*2,l,r);
if(r>mid)ans+=Sum(rt*2+1,l,r);
Pushup(rt);
return ans;
}
 
void dfs1(int u,int fat){
fa[u]=fat;
son[u]=0;
dep[u]=dep[fat]+1;
siz[u]=1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[son[u]]<siz[v])son[u]=v;
}
}
 
void dfs2(int u,int ux){
top[u]=ux;
id[u]=++sn;
pre[sn]=u;
if(son[u])dfs2(son[u],ux);
else return;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==son[u] || v==fa[u])continue;
    dfs2(v,v);
}
}
 
int AddLine(int u){
int ans=0,f=top[u];
while(f!=1){
    ans+=id[u]-id[f]+1-Sum(1,id[f],id[u]);
    Add(1,id[f],id[u]);
    u=fa[f];
    f=top[u];
}
ans+=id[u]-id[1]+1-Sum(1,id[1],id[u]);
Add(1,id[1],id[u]);
return ans;
}
 
int DelSome(int u){
int ans=Sum(1,id[u],id[u]+siz[u]-1);
Del(1,id[u],id[u]+siz[u]-1);
return ans;
}
 
int main(){
freopen("4196.in","r",stdin);
freopen("4196.out","w",stdout);
scanf("%d",&n);
for(int i=2;i<=n;i++){
    int tp;
    scanf("%d",&tp);
    AddEdge(tp+1,i);
}
dfs1(1,0);
dfs2(1,1);
Build(1,1,n);
scanf("%d",&q);
for(int i=1;i<=q;i++){
    char s[10];
    int u;
    scanf("%s %d",s,&u);
    if(s[0]=='i')printf("%d\n",AddLine(u+1));
    else printf("%d\n",DelSome(u+1));
}
return 0;
}