BZOJ 3786星系探索【Splayメンテナンスdfsシーケンス】*

#include
using namespace std;
#define N 200010
#define LL long long
#define pi pair
inline int read(){
    int ans=0,w=1;char c=getchar();
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')w=-1,c=getchar();
    while(isdigit(c))ans=(ans<<1)+(ans<<3)+c-'0',c=getchar();
    return ans*w;
}
inline void print(LL x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)print(x/10);
    putchar((x-(x/10)*10)+'0');
} 
struct Edge{int v,next;}E[N];
int head[N]={0},tot=0;
int n,q,id[N],dfn=0;
int w[N];
pi st[N];
inline void add(int u,int v){
    E[++tot]=(Edge){v,head[u]};
    head[u]=tot;
}
inline void dfs(int u,int fa){
    id[++dfn]=u;
    st[dfn]=(pi){w[u],1};
    for(int i=head[u];i;i=E[i].next)
        if(E[i].v!=fa)dfs(E[i].v,u);
    id[++dfn]=u+n;
    st[dfn]=(pi){-w[u],-1};
}
int root,fa[N],son[N][2],cnt=0;
int tag[N],siz[N],num[N],typ[N];
LL sum[N],val[N];
inline void pushup(int t){
    sum[t]=sum[son[t][0]]+sum[son[t][1]]+val[t];
    siz[t]=siz[son[t][0]]+siz[son[t][1]]+1;
    num[t]=num[son[t][0]]+num[son[t][1]]+typ[t];
}
inline void pushnow(int t,LL vl){
    tag[t]+=vl;
    if(typ[t]>0)val[t]+=vl;
    else val[t]-=vl;
    sum[t]+=vl*num[t];
}
inline void pushdown(int t){
    if(fa[t])pushdown(fa[t]);
    if(tag[t]){
        pushnow(son[t][0],tag[t]);
        pushnow(son[t][1],tag[t]);
        tag[t]=0;
    }
}
inline bool Son(int t){return son[fa[t]][1]==t;}
inline void rotate(int t){
    int f=fa[t],g=fa[f];
    bool a=Son(t),b=a^1;
    if(g)son[g][Son(f)]=t;fa[t]=g;
    son[f][a]=son[t][b];fa[son[f][a]]=f;
    son[t][b]=f;fa[f]=t;
    pushup(f);pushup(t);
}
inline void splay(int t,int tp){
    if(!t)return;
    pushdown(t);
    while(fa[t]!=tp){
        int f=fa[t];
        if(fa[f]!=tp){
            if(Son(t)^Son(f))rotate(t);
            else rotate(f);
        }
        rotate(t);
    }
    if(!tp)root=t;
}
inline int build(int l,int r){
    if(l>r)return 0;
    int mid=(l+r)>>1,t=id[mid];
    val[t]=sum[t]=st[mid].first;
    num[t]=typ[t]=st[mid].second;
    siz[t]=1;tag[t]=0;
    if(l==r)return t;
    fa[son[t][0]=build(l,mid-1)]=t;
    fa[son[t][1]=build(mid+1,r)]=t;
    pushup(t);
    return t;
}
inline int pre(int pos){
    int t=son[pos][0];
    while(son[t][1])t=son[t][1];
    return t;
}
inline int nxt(int pos){
    int t=son[pos][1];
    while(son[t][0])t=son[t][0];
    return t;
} 
inline void modify(int l,int r,LL vl){
    int ll=pre(l),rr=nxt(r);
    splay(ll,0);
    splay(rr,root);
    pushnow(son[son[root][1]][0],vl);
}
inline LL query(int pos){
    splay(pos,0);
    return sum[son[pos][0]]+val[pos];
}
inline void change(int pos,int father){
    int lx=pre(pos),rx=nxt(pos+n);
    splay(lx,0);
    splay(rx,lx);
    int t=son[rx][0];
    fa[t]=0;son[rx][0]=0;
    int lf=nxt(father);
    splay(father,0);
    splay(lf,father);
    son[lf][0]=t;fa[t]=lf;
    pushup(lf);
    pushup(father);
}
int main(){
    n=read();
    for(int i=2;i<=n;i++){
        int x=read();
        add(i,x);add(x,i);
    }
    for(int i=1;i<=n;i++)w[i]=read();
    dfs(1,0);
    id[0]=n*2+1;st[0]=(pi){0,1};
    id[dfn+1]=n*2+2;st[dfn+1]=(pi){0,-1};
    root=build(0,dfn+1);
    int m=read();
    while(m--){
        char c[5];
        scanf("%s",c);
        if(c[0]=='Q'){
            int x=read();
            print(query(x));
            printf("
");
        }else if(c[0]=='C'){
            int x=read(),y=read();
            change(x,y);
        }else{
            int x=read(),y=read();
            modify(x,x+n,y);
        }
    }
    return 0;
}