rt，蒟蒻刚学树剖0.1145141919810ms,求大佬调

提交链接

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct tree{
    long long val,l,r,add;

}t[4*N+10];
//以下为板子，略修改
long long n,m,s,mod=1e9;
long long w[N],w_new[N];
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
void addtag(int p,int d){
    t[p].add=d;
    t[p].val=d*(t[p].r-t[p].l+1);//改
    t[p].val%=mod;
}
void push_up(int p){
    t[p].val=t[ls(p)].val+t[rs(p)].val;
    t[p].val%=mod;
}
void push_down(int p){
    if(t[p].add!=-1){
        addtag(ls(p),t[p].add);
        addtag(rs(p),t[p].add);
        t[p].add=-1;
    }
}
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    t[p].add=-1;
    if(l==r){
        t[p].val=w_new[l];
        t[p].val%=mod;
        return;
    }
    int mid=(t[p].l+t[p].r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    push_up(p);
}
void update(int p,int l,int r,int k){
    if(l<=t[p].l && r>=t[p].r){
        addtag(p,k);
        return;
    }
    push_down(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid)update(ls(p),l,r,k);
    if(r>mid)update(rs(p),l,r,k);
    push_up(p);
}
int query(int p,int l,int r){
    if(l<=t[p].l && r>=t[p].r){
        return t[p].val%=mod;
    }
    push_down(p);
    int ans=0;
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid)ans+=query(ls(p),l,r);
    if(r>mid)ans+=query(rs(p),l,r);
    return ans;
}

struct node{
    int to,nxt;
}edge[2*N];
int cnt,head[N*2];
void prework(){
    for(int i=0;i<N*2;i++){
        head[i]=-1;edge[i].nxt=-1;
    }
    cnt=0;
}
void adg(int u,int v){
    edge[cnt].to=v,edge[cnt].nxt=head[u],head[u]=cnt++;
}
int dep[N],siz[N],son[N],top[N],fat[N],id[N];
int num=0;
void dfs1(int u,int fa){
    dep[u]=dep[fa]+1;
    fat[u]=fa;
    siz[u]=1;
    for(int i=head[u];~i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v!=fa){
            fat[v]=u;
            dfs1(v,u);
            siz[u]+=siz[v];
            if(!son[u]||siz[son[u]]<siz[v])
                son[u]=v;
        }
    }
}
void dfs2(int x,int topx){
    id[x]=++num;
    w_new[num]=w[x];
    top[x]=topx;
    if(!son[x])return;
    dfs2(son[x],topx);
    for(int i=head[x];~i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v!=fat[x] && v!=son[x]){
            dfs2(v,v);
        }
    }
}
void update_range(int x,int y,int z){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,id[top[x]],id[x],z);
        x=fat[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(1,id[x],id[y],z);
}
int query_range(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans+=query(1,id[top[x]],id[x]);
        ans%=mod;
        x=fat[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans+=query(1,id[x],id[y]);
    return ans%mod;
}
void update_tree(int x,int k){
    update(1,id[x],id[x]+siz[x]-1,k);
}
int query_tree(int x){
    return query(1,id[x],id[x]+siz[x]-1)%mod;
}
//以上为板子
signed main(){
    prework();
    cin>>n;s=1;
    for(int i=1;i<=n-1;i++){
        int temp;
        cin>>temp;
        adg(temp+1,i+1);
    }
    dfs1(s,1);
    dfs2(s,s);
    build(1,1,n-1);
    string op;int x;
    cin>>m;
    while(m--){
        cin>>op>>x;
        x+=1;
        if(op=="install"){
            int now=t[1].val;
            update_range(1,x,1);
            int temp=t[1].val;
            
            cout<<abs(temp-now)<<'\n';
        }
        else{
            int now=t[1].val;
            update_tree(x,0);
            int temp=t[1].val;
            
            cout<<abs(temp-now)<<'\n';
        }
    }
    
    return 0;
}