[BZOJ3786] 星系探索

[BZOJ3786] 星系探索

Description

物理学家小C的研究正遇到某个瓶颈。他正在研究的是一个星系，这个星系中有n个星球，其中有一个主星球(方便起见我们默认其为1号星球)，其余的所有星球均有且仅有一个依赖星球。主星球没有依赖星球。我们定义依赖关系如下：若星球a的依赖星球是b,则有星球a依赖星球b.此外，依赖关系具有传递性，即若星球a依赖星球b,星球b依赖星球c,则有星球a依赖星球c.
对于这个神秘的星系中，小C初步探究了它的性质，发现星球之间的依赖关系是无环的。并且从星球a出发只能直接到达它的依赖星球b.
每个星球i都有一个能量系数wi.小C想进行若干次实验，第i次实验，他将从飞船上向星球di发射一个初始能量为0的能量收集器，能量收集器会从星球di开始前往主星球，并收集沿途每个星球的部分能量，收集能量的多少等于这个星球的能量系数。但是星系的构成并不是一成不变的，某些时刻，星系可能由于某些复杂的原因发生变化。有些时刻，某个星球能量激发，将使得所有依赖于它的星球以及他自己的能量系数均增加一个定值。还有可能在某些时刻，某个星球的依赖星球会发生变化，但变化后依然满足依赖关系是无环的。现在小C已经测定了时刻0时每个星球的能量系数,以及每个星球(除了主星球之外)的依赖星球。接下来的m个时刻，每个时刻都会发生一些事件。其中小C可能会进行若干次实验，对于他的每一次实验，请你告诉他这一次实验能量收集器的最终能量是多少。

Input

第一行一个整数n,表示星系的星球数。接下来n-1行每行一个整数,分别表示星球2-n的依赖星球编号。接下来一行n个整数，表示每个星球在时刻0时的初始能量系数wi.
接下来一行一个整数m,表示事件的总数。事件分为以下三种类型。(1)"Q di"表示小C要开始一次实验,收集器的初始位置在星球di.
(2)"C xi yi"表示星球xi的依赖星球变为了星球yi.
(3)"F pi qi"表示星球pi能量激发，常数为qi.

Output

对于每一个事件类型为Q的事件，输出一行一个整数，表示此次实验的收集器最终能量。

Sample Input

3
1
1
4 5 7
5
Q 2
F 1 3
Q 2
C 2 3
Q 2

Sample Output

9
15
25

HINT

n<=100000,m<=300000,1<di,xi<=n,wi,qi<=100000.保证操作合法。注意w_i>=0

试题分析

欧拉序是一个好东西，我们将dfs序所有点扔到splay中(出栈也算，权值为负)。
那么我们求从1到当前点的距离就是一个前缀和。
这样splay移动子树，子树加就可以了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
 
using namespace std;
#define LL long long
 
inline int read(){
    int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int INF = 2147483600;
const int MAXN = 100100;
 
int N,M; vector<int> vec[MAXN+1]; int a[MAXN+1];
int ch[MAXN<<1][2]; LL val[MAXN<<1],s[MAXN<<1]; LL sz[MAXN<<1],su[MAXN<<1];
int sta[MAXN<<1]; int tim; bool vis[MAXN<<1];
int L[MAXN+1],R[MAXN+1]; char opr[5];
int cnt; LL op[MAXN<<1]; int root; LL col[MAXN<<1];
int fa[MAXN<<1]; LL b[MAXN<<1];
 
inline void dfs(int k){
    b[++tim]=a[k]; L[k]=tim; vis[tim]=true;
    for(int i=0;i<vec[k].size();i++){
        int v=vec[k][i]; dfs(v);
    }  b[++tim]=a[k]; R[k]=tim; vis[tim]=false; return ;
}
inline void add(int k,int x){
    if(!k) return ; s[k]+=1LL*su[k]*x;
    val[k]+=1LL*op[k]*x;
    col[k]+=x; return ;
}
inline void pushdown(int x){
    if(col[x]){
        if(ch[x][0]) add(ch[x][0],col[x]);
        if(ch[x][1]) add(ch[x][1],col[x]);
        col[x]=0;
    }
}
inline void Con(int s,int f,int c){if(f) ch[f][c]=s; if(s) fa[s]=f; return ;}
inline void update(int x){
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; 
    s[x]=s[ch[x][0]]+s[ch[x][1]]+val[x];  //cout<<"x:"<<op[x]*val[x]<<endl;
    su[x]=su[ch[x][0]]+su[ch[x][1]]+op[x]; 
    return ;
}
inline bool chd(int x){return ch[fa[x]][0]==x?0:1;}
inline void rotate(int x){
    int Fa=fa[x],grfa=fa[Fa]; int cfa=chd(Fa),cx=chd(x); int B=ch[x][cx^1];
    Con(Fa,x,cx^1); Con(x,grfa,cfa); Con(B,Fa,cx); 
    update(Fa); update(x); return ;
}
inline void Splay(int x,int farot,int &rot){
    if(x==rot) return ; int top=0,y=x;
    for(int y=x;y;y=fa[y]) sta[++top]=y;
    for(int i=top;i>=1;i--) pushdown(sta[i]);
    while(fa[x]!=farot){
        int y=fa[x]; if(fa[y]==farot) rotate(x);
        else {
            rotate((chd(x)==0)^(chd(y)==0)?x:y);
            rotate(x);
        }
    } rot=x;
    return ;
}
inline void build(int &k,int l,int r){
    int mid=(l+r)>>1; k=mid; op[k]=(vis[k]?1:-1); val[k]=b[k]*op[k];
    if(l<mid) build(ch[k][0],l,mid-1),fa[ch[k][0]]=k;
    if(r>mid) build(ch[k][1],mid+1,r),fa[ch[k][1]]=k;
    update(k); return ;
}
inline int Pre(int x){
    Splay(x,0,root);
    for(x=ch[root][0];ch[x][1];x=ch[x][1]);
    Splay(x,0,root); return x;
}
inline int Nxt(int x){
    Splay(x,0,root); 
    for(x=ch[root][1];ch[x][0];x=ch[x][0]);
    Splay(x,0,root); return x;
}
inline void split(int l,int r){
    int ll=Pre(l),rr=Nxt(r);
    Splay(ll,0,root); Splay(rr,root,ch[root][1]);
    return ;
}
inline void Add(int x,int c){
    split(L[x],R[x]); int rc=ch[root][1];
    add(ch[rc][0],c); update(rc); 
    update(root); return ;
}
inline LL Query(int r){
    split(L[1],L[r]); int rc=ch[root][1];
    return s[ch[rc][0]];
} 
inline void Change(int x,int y){
    split(L[x],R[x]); int now=ch[ch[root][1]][0];
    fa[now]=0; ch[ch[root][1]][0]=0; update(ch[root][1]); update(root);
    int l=L[y],r=Nxt(l); Splay(l,0,root); Splay(r,root,ch[root][1]);
    ch[ch[root][1]][0]=now; fa[now]=ch[root][1]; 
    update(ch[root][1]); update(root);
}
 
int main(){
    N=read();
    for(int i=2;i<=N;i++){
        int x=read(); vec[x].push_back(i);
    }for(int i=1;i<=N;i++) a[i]=read(); 
    sta[++tim]=0; dfs(1); sta[++tim]=0;
    build(root,1,tim);
    M=read(); while(M--){
        scanf("%s",opr);
        if(opr[0]=='Q'){
            int x=read();
            printf("%lld
",Query(x));
        }
        else if(opr[0]=='C'){
            int x=read(),y=read();
            Change(x,y);
        }
        else if(opr[0]=='F'){
            int x=read(),k=read();
            Add(x,k);
        }
    } 
    return 0;
}