[文章目录]
Description
给定一个n节点有点权的树，有以下m次操作。
1.一个节点的子树上（包括自己）的所有节点点权加一个定值.
2.移动子树到另一个节点下方。
3.查询某一结点到根节点的路径上的点权和
（n<=100000,m<=300000）
有个叫dfs序的东西，本题要用到。
先想到要维护点权加和，还要有移动。splay啊。但是维护的东西要使得能求出区间和，就是点到根节点的路径上的点权和。
选择维护dfs的出栈入栈序，出栈权值为负，那么点到根节点的路径的点权和就是概数列的前缀和（好玄学的东西，想想就觉得好神奇）。然后一个节点的子树恰好也在一个连续区间里，就是时间戳在节点的入栈出栈内的点。移动的话直接移动就好了，移到该区间的入站时间戳的后边。不要忘了修改fa。
另外加值的时候由于要一下更新好该节点的所有参数，所以维护一个系数的和，这样的话，该节点子树点权和+的就是系数的和*增加的值。
不同的一点就是写了一个找前面元素指针和后面元素指针的函数（由于只能获得闭区间的端点指针），还有就是由于要push_down，所以从一个节点直接向上爬到根，放到一个麻袋里，然后一个个取出下传。
还有什么long long的东西
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define N 101000
using namespace std;
LL n,m,k1,k2;
char st[20];
LL head[N],to[N],nxt[N],cnt;
LL val[N];
void add_edge(LL x,LL y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
struct node
{
node *fa,*c[2];
LL flag;
LL add,val,sum,fsum;//系数的和
node(LL x,LL y);
void push_up();
void push_down();
void all_add(LL x);
}*null=new node(0,0),*root,*a[201000],*fro;
LL in[N],out[N],tot,top;//in[]为入站时间戳，out[]为出栈时间戳
node *zan[N];
void node :: all_add(LL x)
{
sum+=x*fsum;
val+=x; //这里智障的一开始写成x*flag了。
add+=x;
}
node :: node(LL x,LL y)
{
fa=c[0]=c[1]=null;
val=x;
fsum=flag=y;
add=0;
sum=y*x;
}
void node::push_up()
{
fsum=c[0]->fsum+c[1]->fsum+flag;
sum=c[0]->sum+c[1]->sum+val*flag;
}
void node::push_down()
{
if(add)
{
if(c[0]!=null) c[0]->all_add(add);
if(c[1]!=null) c[1]->all_add(add);
add=0;
}
}
node *front(node *x)//前驱指针
{
if(x->c[0]!=null)
{
x=x->c[0];
while(x->c[1]!=null) x=x->c[1];
return x;
}
while(x==x->fa->c[0]) x=x->fa;
return x->fa;
}
node *after(node *x)//后继指针
{
if(x->c[1]!=null)
{
x=x->c[1];
while(x->c[0]!=null) x=x->c[0];
return x;
}
while(x==x->fa->c[1]) x=x->fa;
return x->fa;
}
node * build(LL l,LL r)
{
if(l>r) return null;
LL mid=l+r>>1; node *re=a[mid];
re->c[0]=build(l,mid-1);re->c[1]=build(mid+1,r);
re->c[0]->fa=re;re->c[1]->fa=re;
re->push_up();return re;
}
void initialize()
{
fro=root=new node(0,0);
root->c[1]=new node(0,0);
root->c[1]->fa=root;
root->c[1]->c[0]=build(1,tot);
root->c[1]->c[0]->fa=root->c[1];
root->c[1]->push_up();
root->push_up();
}
void rotate(node *x)
{
node *y=x->fa;LL l=(x==y->c[1]),r=l^1;
y->c[l]=x->c[r];x->c[r]->fa=y;
x->c[r]=y;x->fa=y->fa;
if(y==y->fa->c[l]) y->fa->c[l]=x;
else y->fa->c[r]=x;
y->fa=x;y->push_up();x->push_up();
if(y==root) root=x;
}
LL read()
{
char ch=getchar();LL re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
void dfs(LL x)//dfs出栈入栈序
{
a[++tot]=new node(val[x],1);in[x]=tot;//入 系数为1
for(LL i=head[x];i;i=nxt[i]) dfs(to[i]);
out[x]=++tot; a[tot]=new node(val[x],-1);//出 系数为 -1
}
void dfs_check(node *x)
{
if(x==null) return ;
x->push_down();
dfs_check(x->c[0]);
printf("%lld %lld ls %lld rs %lld fsum %lld sum %lld add %lld\n",x->val,x->flag,x->c[0]->val,x->c[1]->val,x->fsum,x->sum,x->add);
dfs_check(x->c[1]);
}
void splay(node *x,node *tar)
{
while(1)
{
node *y=x->fa,*z=y->fa;
if(y==tar) break;
if(z==tar){rotate(x);break;}
if((x==y->c[0])^(y==z->c[0])==0) rotate(y);
else rotate(x); rotate(x);
}
}
void find(node *x,node *z)//自底向上
{
top=0;
while(x!=null) {zan[++top]=x;x=x->fa;}
while(top) {zan[top]->push_down();top--;}
splay(zan[1],z);
}
int main()
{
n=read();
for(LL x,i=2;i<=n;i++){x=read();add_edge(x,i);}
for(LL i=1;i<=n;i++) val[i]=read();
dfs(1);
initialize();
//dfs_check(root);
m=read();
while(m--)
{
scanf("%s",st);k1=read();
switch(st[0])
{
case 'Q':
{
find(fro,null);
find(after(a[in[k1]]),root);
//dfs_check(root);
printf("%lld\n",root->c[1]->c[0]->sum);
break;
}
case 'F':
{
k2=read();
find(front(a[in[k1]]),null);
find(after(a[out[k1]]),root);
root->c[1]->c[0]->all_add(k2);
root->c[1]->push_up();
root->push_up();
break;
}
case 'C':
{
k2=read();
find(front(a[in[k1]]),null);
find(after(a[out[k1]]),root);
node *tmp=root->c[1]->c[0];
root->c[1]->c[0]=null;
root->c[1]->push_up();root->push_up();
find(a[in[k2]],null);
find(after(a[in[k2]]),root);
root->c[1]->c[0]=tmp;
tmp->fa=root->c[1];//重中之重
root->c[1]->push_up();root->push_up();
break;
}
}
//dfs_check(root);
}
return 0;
}