【题意】给定一棵带点权树，三种操作：
1.询问点x到根的路径和
2.子树x内的点权加定值y
3.将点x的父亲更换为y，保证仍是树。
【算法】平衡树（fhq-treap）
【题解】
将树的dfs序作为序列维护，对每个点入栈+1，出栈-1，这样操作1就是前缀和（非此路径的都会正负抵消），操作2就是区间加值，操作3就是区间移动，可以用平衡树维护。
具体实现：原树上每个点在序列中对应两个点（入栈和出栈），每个点维护自身系数（1或-1），自身数值（含系数），系数和，数值和。维护系数是为了满足通过标记直接修改sum。
还有一个问题，只知道点的编号如何查询点的排名，实际上就是左子树+往上左走时的所有左子树（均含本点）。
过程中，在up处更新左右节点的父亲即可，但要额外更新分裂合并时根节点的父亲。
记得开long long。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=;
struct cyc{int l,r,rnd,sz,fa,gnum,gsum;ll delta,num,sum;}t[maxn];
struct edge{int v,from;}e[maxn];
int tote=,first[maxn];
void insert(int u,int v){tote++;e[tote].v=v;e[tote].from=first[u];first[u]=tote;}
int n,m,be[maxn],ed[maxn],tot,a[maxn],b[maxn],c[maxn],st[maxn],root;
int read(){
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
void dfs(int x){
be[x]=++tot;b[tot]=;c[tot]=a[x];
for(int i=first[x];i;i=e[i].from){
dfs(e[i].v);
}
ed[x]=++tot;b[tot]=-;c[tot]=-a[x];
}
void up(int k){
t[k].sz=+t[t[k].l].sz+t[t[k].r].sz;
t[k].gsum=t[k].gnum+t[t[k].l].gsum+t[t[k].r].gsum;
t[k].sum=t[k].num+t[t[k].l].sum+t[t[k].r].sum;
if(t[k].l)t[t[k].l].fa=k;
if(t[k].r)t[t[k].r].fa=k;
}
void modify(int k,int x){t[k].num+=1ll*t[k].gnum*x;t[k].sum+=1ll*t[k].gsum*x;t[k].delta+=x;}
void down(int k){
if(t[k].delta){
modify(t[k].l,t[k].delta);modify(t[k].r,t[k].delta);
t[k].delta=;
}
}
void DFS(int k){
if(!k)return;
DFS(t[k].l);DFS(t[k].r);
up(k);
}
void build(){
int top=;
for(int i=;i<=tot;i++){
t[i]=(cyc){,,rand(),,,b[i],b[i],,c[i],c[i]};
while(top&&t[st[top]].rnd>t[i].rnd){
t[st[top]].r=t[i].l;
t[i].l=st[top--];
}
t[st[top]].r=i;
st[++top]=i;
}
t[]=(cyc){,,,,,,,,};
DFS(root=st[]);
t[root].fa=;
}
int find(int x){
int sum=t[t[x].l].sz+;
while(t[x].fa!=){
if(t[t[x].fa].r==x)sum+=t[t[t[x].fa].l].sz+;
x=t[x].fa;
}
return sum;
}
int merge(int a,int b){
if(!a||!b)return a^b;
if(t[a].rnd<t[b].rnd){
down(a);
t[a].r=merge(t[a].r,b);
up(a);
return a;
}
else{
down(b);
t[b].l=merge(a,t[b].l);
up(b);
return b;
}
}
void split(int k,int &l,int &r,int x){
if(!k)return void(l=r=);
down(k);
if(x<t[t[k].l].sz+){
r=k;
split(t[k].l,l,t[k].l,x);
}
else{
l=k;
split(t[k].r,t[k].r,r,x-t[t[k].l].sz-);
}
up(k);
}
ll goroot(int x){
int a,b;
split(root,a,b,find(be[x]));
ll ans=t[a].sum;
root=merge(a,b);
t[root].fa=;
return ans;
}
void change(int x,int y){
int a,b,c;
split(root,b,c,find(ed[x]));t[b].fa=t[c].fa=;
split(b,a,b,find(be[x])-);t[a].fa=t[b].fa=;
modify(b,y);
root=merge(a,b);
root=merge(root,c);
t[root].fa=;
}
void move(int x,int y){
int a,b,c;
split(root,b,c,find(ed[x]));t[b].fa=t[c].fa=;
split(b,a,b,find(be[x])-);t[a].fa=t[b].fa=;
root=merge(a,c);
t[root].fa=;
split(root,a,c,find(be[y]));t[a].fa=t[c].fa=;
root=merge(a,b);
root=merge(root,c);
t[root].fa=;
}
char s[];
int main(){
srand();
n=read();
for(int i=;i<=n;i++)insert(read(),i);
for(int i=;i<=n;i++)a[i]=read();
dfs();build();
m=read();
for(int i=;i<=m;i++){
scanf("%s",s);
int x=read();
if(s[]=='Q'){
printf("%lld\n",goroot(x));
}
if(s[]=='C'){
int y=read();
move(x,y);
}
if(s[]=='F'){
int y=read();
change(x,y);
}
}
return ;
}