( ext{Description})
( ext{Solution})
据说是伪 ( ext{ETT})。
但既然不会那玩意儿，所以把它称作——欧拉序 (+) 平衡树。
具体怎么做呢？我们设点 (u) 的进入，出去的时间戳为 (st_u,ed_u)。然后在欧拉序序列上建一棵平衡树，给 (st_u) 的权值赋为 (val_u)，给 (ed_u) 的权值赋为 (-val_u)。
- ( ext Q)：就是查询点 (d) 与点 (1) 的权值和，我们把它转化成求 ([st_1,st_d]) 的权值和。可以看作在栈里加点，弹点（遇 (st) 加入，遇 (ed) 弹出），实际上栈里的点就是 (1,d) 的路径。我们给 (st,ed) 赋值相反数的操作其实是为了模拟弹栈（所以实际上这个题可以是查询一段路径的权值和）。
- ( ext C)：其实是把以 (x) 为根的子树变成 (y) 的儿子。因为表示 (x) 为根子树的欧拉序序列是连续且为 ([st_x,ed_x])，我们可以把这段区间移到 (st_y) 的后面，这个用平衡树维护。
- ( ext F)：把 ([st_p,ed_p]) 代表的节点加上 (q) 即可。
详见代码。
( ext{Code})
#include <cstdio>
#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
typedef long long ll;
const int maxn=1e5+5;
int head[maxn],nxt[maxn],to[maxn],cnt,n,m,idx=1,Val[maxn<<1],l[maxn],r[maxn],a[maxn];
char str[10];
struct Splay {
int rt;
struct node {
int pos,neg,val,son[2],op,f;
ll sum,tag;
/*
pos 与 neg：自己为根的子树有多少个 st/ed，这个是用来算加 k 值时的正负。
*/
} t[maxn<<1];
bool dir(int x) {return t[t[x].f].son[1]==x;}
void add(int x,int fa,bool dir) {
if(x) t[x].f=fa;
if(fa) t[fa].son[dir]=x;
}
void upd(int o,int k) {
if(!o) return;
t[o].tag+=k;
t[o].sum+=1ll*k*(t[o].pos-t[o].neg);
t[o].val+=1ll*k*t[o].op;
}
void pushDown(int o) {
if(!o||(!t[o].tag)) return;
upd(t[o].son[0],t[o].tag),upd(t[o].son[1],t[o].tag);
t[o].tag=0;
}
void pushUp(int o) {
if(!o) return;
t[o].sum=t[t[o].son[0]].sum+t[t[o].son[1]].sum+t[o].val;
t[o].pos=t[t[o].son[0]].pos+t[t[o].son[1]].pos+(t[o].op==1);
t[o].neg=t[t[o].son[0]].neg+t[t[o].son[1]].neg+(t[o].op==-1);
}
void rotate(int x) {
int fa=t[x].f,ffa=t[fa].f,dx=dir(x),df=dir(fa);
pushDown(fa),pushDown(x);
add(t[x].son[dx^1],fa,dx);
add(fa,x,dx^1);
add(x,ffa,df);
pushUp(fa),pushUp(x);
}
void splay(int x,int goal) {
for(int fa;(fa=t[x].f)^goal;rotate(x))
if(t[fa].f^goal) rotate(dir(x)==dir(fa)?fa:x);
if(!goal) rt=x;
}
int pre(int x) {x=t[x].son[0]; while(t[x].son[1]) x=t[x].son[1]; return x;}
int suf(int x) {x=t[x].son[1]; while(t[x].son[0]) x=t[x].son[0]; return x;}
void Build(int &o,int l,int r,int fa) {
o=l+r>>1; t[o].f=fa;
if(Val[o]>0) t[o].op=1,t[o].val=Val[o]-1;
else t[o].op=-1,t[o].val=Val[o]+1;
if(l<o) Build(t[o].son[0],l,o-1,o);
if(r>o) Build(t[o].son[1],o+1,r,o);
pushUp(o);
}
ll Query(int u) {
int x,y;
splay(l[1],0),x=pre(l[1]);
splay(l[u],0),y=suf(l[u]);
splay(x,0),splay(y,x);
return t[t[y].son[0]].sum;
}
void Add(int u,int k) {
int x,y;
splay(l[u],0),x=pre(l[u]);
splay(r[u],0),y=suf(r[u]);
splay(x,0),splay(y,x);
upd(t[y].son[0],k),pushDown(t[y].son[0]);
}
void Modify(int u,int v) {
int x,y;
splay(l[u],0),x=pre(l[u]);
splay(r[u],0),y=suf(r[u]);
splay(x,0),splay(y,x);
int Son=t[y].son[0]; t[Son].f=t[y].son[0]=0; pushUp(y);
splay(l[v],0);
int nxt=suf(l[v]); splay(nxt,l[v]);
t[Son].f=nxt,t[nxt].son[0]=Son;
pushUp(Son),pushUp(nxt);
}
} T;
void addEdge(int u,int v) {
nxt[++cnt]=head[u],to[cnt]=v,head[u]=cnt;
}
void dfs(int u) {
l[u]=++idx,Val[idx]=a[u]+1;
erep(i,u) dfs(to[i]);
r[u]=++idx,Val[idx]=-a[u]-1;
}
int main() {
int x,y;
n=read(9);
rep(i,2,n) x=read(9),addEdge(x,i);
rep(i,1,n) a[i]=read(9);
dfs(1);
T.Build(T.rt,1,idx+1,0);
for(int m=read(9);m;--m) {
scanf("%s",str); x=read(9);
if(str[0]=='Q') print(T.Query(x),'
');
else if(str[0]=='C') y=read(9),T.Modify(x,y);
else y=read(9),T.Add(x,y);
}
return 0;
}