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
1
1
4 5 7
5
Q 2
F 1 3
Q 2
C 2 3
Q 2
Sample Output
9
15
25
15
25
HINT
n<=100000,m<=300000,1<di,xi<=n,wi,qi<=100000.保证操作合法。注意w_i>=0。
纪念一下一道调了两天发现自己忘开long long的题>_<
简单地写一下题解吧。
首先，为了将子树变成一段连续的区间，我们需要将每个点拆成两个，一个代表入栈，一个代表出栈。入栈时点权为正，出栈时为负，这样一个点到根节点的路径上的点权和等于前缀和。先在整棵树上dfs，把这些点塞进一个队列里，根据队列把树建好，然后就是疯狂地拆拆拆和splay。
fhq-treap分裂过程中记录父亲【Time:32912ms】（因为多了一个find函数还需要记一下父亲）
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#define LL long long
using namespace std;
const int N=2e5+;
int n,m,cnt,tmp,x,y,root,rt1,rt2,rt3;
int st[N],q[N],first[N],ch[N][];
LL sh[N][];
char op[];
struct edge{int to,next;}e[N];
#define lc ch][0
#define rc ch][1
#define rnd ch][2
#define sz ch][3
#define xi ch][4
#define num ch][5
#define fa ch][6
#define v sh][0
#define sum sh][1
#define tag sh][2
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
void ins(int from,int to){e[++cnt]=(edge){to,first[from]};first[from]=cnt;}
void dfs(int x)
{
q[++cnt]=x;
for(int i=first[x];i;i=e[i].next)dfs(e[i].to);
q[++cnt]=x+n;
}
void up(int w)
{
int l=w[lc],r=w[rc];
w[sz]=l[sz]+r[sz]+;
w[num]=l[num]+r[num]+w[xi];
w[sum]=l[sum]+r[sum]+w[v];
}
void dn(int w)
{
int l=w[lc],r=w[rc];LL t=w[tag];
if(!t)return;w[tag]=;
if(l)l[tag]+=t,l[v]+=t*l[xi],l[sum]+=t*l[num];
if(r)r[tag]+=t,r[v]+=t*r[xi],r[sum]+=t*r[num];
// printf("l:%d xi:%d r:%d xi:%d\n",l,l[xi],r,r[xi]);
}
void check(int w){if(!w)return;check(w[lc]);check(w[rc]);up(w);}
int build(int n)
{
int top=,w;
for(int i=;i<=n;i++)
{
w=q[i];w[rnd]=rand();
while(top&&st[top][rnd]>w[rnd])
{
w[lc][fa]=st[top];st[top][rc]=w[lc];
st[top][fa]=w;w[lc]=st[top--];
}
w[fa]=st[top];st[top][rc]=w;st[++top]=w;
}
ch[][]=;st[][fa]=;check(st[]);
return st[];
}
void split(int w,int& l,int fal,int& r,int far,int k)
{
if(!w){l=r=;return;}
dn(w);int lson=w[lc][sz];
if(k<=lson)w[fa]=far,r=w,split(w[lc],l,fal,w[lc],w,k);
else w[fa]=fal,l=w,split(w[rc],w[rc],w,r,far,k-lson-);
up(w);
}
int merge(int a,int b)
{
if(!a||!b)return a+b;
if(a[rnd]<b[rnd]){dn(a);a[rc]=merge(a[rc],b);a[rc][fa]=a;up(a);return a;}
else {dn(b);b[lc]=merge(a,b[lc]);b[lc][fa]=b;up(b);return b;}
}
int find(int x)
{
int ans=x[lc][sz]+;
while(x[fa])
{
if(x[fa][rc]==x)ans+=x[fa][lc][sz]+;
x=x[fa];
}
return ans;
}
void query()
{
x=read();rt1=rt2=;split(root,rt1,,rt2,,find(x));
printf("%lld\n",rt1[sum]);root=merge(rt1,rt2);
}
void change()
{
x=read();y=read();rt1=rt2=rt3=;
split(root,rt1,,rt3,,find(x+n));
root=rt1;rt1=;split(root,rt1,,rt2,,find(x)-);
root=merge(rt1,rt3);rt1=rt3=;
split(root,rt1,,rt3,,find(y));
root=merge(rt1,rt2);root=merge(root,rt3);
}
void add()
{
x=read();y=read();rt1=rt2=rt3=;
split(root,rt1,,rt3,,find(x+n));
root=rt1;rt1=;split(root,rt1,,rt2,,find(x)-);
int w=rt2;w[tag]+=y;w[v]+=y*w[xi];w[sum]+=1ll*y*w[num];
root=merge(rt1,rt2);root=merge(root,rt3);
}
void print(int w,int dir)
{
if(!w)return;
if(dir==)printf("from-left ");
if(dir==)printf("from-right ");
printf("[%d] fa:%d v:%lld sum:%lld lson:%d rson:%d\n",w,w[fa],w[v],w[sum],w[lc],w[rc]);
print(w[lc],);print(w[rc],);
}
int main()
{
n=read();
for(int i=;i<=n;i++)tmp=read(),ins(tmp,i);
for(int i=;i<=n;i++)tmp=read(),i[v]=tmp,(i+n)[v]=-tmp,i[xi]=,(i+n)[xi]=-;
cnt=;dfs();root=build(n*);m=read();//print(root,-1);
while(m--)
{
scanf("%s",op+);
if(op[]=='Q')query();
else if(op[]=='C')change();
else add();
// print(root,-1);
}
return ;
}
fhq-treap up时更新父亲【Time:37452ms】（分裂出来的根节点的父亲记得清零）
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#define LL long long
using namespace std;
const int N=2e5+;
int n,m,cnt,tmp,x,y,root,rt1,rt2,rt3;
int st[N],q[N],first[N],ch[N][];
LL sh[N][];
char op[];
struct edge{int to,next;}e[N];
#define lc ch][0
#define rc ch][1
#define rnd ch][2
#define sz ch][3
#define xi ch][4
#define num ch][5
#define fa ch][6
#define v sh][0
#define sum sh][1
#define tag sh][2
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
void ins(int from,int to){e[++cnt]=(edge){to,first[from]};first[from]=cnt;}
void dfs(int x)
{
q[++cnt]=x;
for(int i=first[x];i;i=e[i].next)dfs(e[i].to);
q[++cnt]=x+n;
}
void up(int w)
{
int l=w[lc],r=w[rc];
w[sz]=l[sz]+r[sz]+;
w[num]=l[num]+r[num]+w[xi];
w[sum]=l[sum]+r[sum]+w[v];
if(l)l[fa]=w;if(r)r[fa]=w;
}
void dn(int w)
{
int l=w[lc],r=w[rc];LL t=w[tag];
if(!t)return;w[tag]=;
if(l)l[tag]+=t,l[v]+=t*l[xi],l[sum]+=t*l[num];
if(r)r[tag]+=t,r[v]+=t*r[xi],r[sum]+=t*r[num];
}
void check(int w){if(!w)return;check(w[lc]);check(w[rc]);up(w);}
int build(int n)
{
int top=,w;
for(int i=;i<=n;i++)
{
w=q[i];w[rnd]=rand();
while(top&&st[top][rnd]>w[rnd])st[top][rc]=w[lc],w[lc]=st[top--];
st[top][rc]=w;st[++top]=w;
}
ch[][]=;st[][fa]=;check(st[]);
return st[];
}
void split(int w,int& l,int fal,int& r,int far,int k)
{
if(!w){l=r=;return;}
dn(w);int lson=w[lc][sz];
if(k<=lson)r=w,split(w[lc],l,fal,w[lc],w,k);
else l=w,split(w[rc],w[rc],w,r,far,k-lson-);
up(w);
}
int merge(int a,int b)
{
if(!a||!b)return a+b;
if(a[rnd]<b[rnd]){dn(a);a[rc]=merge(a[rc],b);up(a);return a;}
else {dn(b);b[lc]=merge(a,b[lc]);up(b);return b;}
}
int find(int x)
{
int ans=x[lc][sz]+;
while(x[fa])
{
if(x[fa][rc]==x)ans+=x[fa][lc][sz]+;
x=x[fa];
}
return ans;
}
void query()
{
x=read();rt1=rt2=;split(root,rt1,,rt2,,find(x));
rt1[fa]=rt2[fa]=;printf("%lld\n",rt1[sum]);root=merge(rt1,rt2);root[fa]=;
}
void change()
{
x=read();y=read();rt1=rt2=rt3=;
split(root,rt1,,rt3,,find(x+n));
rt1[fa]=rt3[fa]=;root=rt1;rt1=;
split(root,rt1,,rt2,,find(x)-);
rt1[fa]=rt2[fa]=;root=merge(rt1,rt3);rt1=rt3=;
split(root,rt1,,rt3,,find(y));
root=merge(rt1,rt2);root=merge(root,rt3);root[fa]=;
}
void add()
{
x=read();y=read();rt1=rt2=rt3=;
split(root,rt1,,rt3,,find(x+n));
rt1[fa]=rt3[fa]=;root=rt1;rt1=;
split(root,rt1,,rt2,,find(x)-);rt1[fa]=rt2[fa]=;
int w=rt2;w[tag]+=y;w[v]+=y*w[xi];w[sum]+=1ll*y*w[num];
root=merge(rt1,rt2);root=merge(root,rt3);root[fa]=;
}
int main()
{
n=read();
for(int i=;i<=n;i++)tmp=read(),ins(tmp,i);
for(int i=;i<=n;i++)tmp=read(),i[v]=tmp,(i+n)[v]=-tmp,i[xi]=,(i+n)[xi]=-;
cnt=;dfs();
root=build(n*);m=read();
while(m--)
{
scanf("%s",op+);
if(op[]=='Q')query();
else if(op[]=='C')change();
else add();
}
return ;
}
splay直接查找前驱后继【Time:25484 ms】（数组版仿佛很容易TLE……慎重）
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=;
struct node{int ch[],size,fa,t,num;long long v,sum,tag;}tr[N<<];
struct edge{int next,to;}e[N];
int n,m,f,root,cnt;
int head[N],q[N<<],s[N];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
void insert(int a,int b){cnt++;e[cnt].to=b;e[cnt].next=head[a];head[a]=cnt;}
void dfs(int x)
{
q[++cnt]=x+;
for(int i=head[x];i;i=e[i].next)dfs(e[i].to);
q[++cnt]=x+n+;
}
void pushup(int x)
{
int l=tr[x].ch[],r=tr[x].ch[];
tr[x].size=tr[l].size+tr[r].size+;
tr[x].num=tr[l].num+tr[r].num+tr[x].t;
tr[x].sum=tr[l].sum+tr[r].sum+tr[x].v;
}
void pushdown(int x)
{
int l=tr[x].ch[],r=tr[x].ch[];long long tag=tr[x].tag;
if(l)tr[l].tag+=tag,tr[l].sum+=tag*tr[l].num,tr[l].v+=tag*tr[l].t;
if(r)tr[r].tag+=tag,tr[r].sum+=tag*tr[r].num,tr[r].v+=tag*tr[r].t;
tr[x].tag=;
}
void rotate(int x,int& k)
{
int y=tr[x].fa,z=tr[y].fa,l,r;
if(tr[y].ch[]==x)l=;else l=;r=l^;
if(y==k)k=x;
else{if(tr[z].ch[]==y)tr[z].ch[]=x;else tr[z].ch[]=x;}
tr[x].fa=z;tr[y].fa=x;tr[tr[x].ch[r]].fa=y;
tr[y].ch[l]=tr[x].ch[r];tr[x].ch[r]=y;
pushup(y);pushup(x);
}
void splay(int x,int& k)
{
int top=;s[++top]=x;
for(int i=x;tr[i].fa;i=tr[i].fa)s[++top]=tr[i].fa;
for(int i=top;i;i--)if(tr[s[i]].tag)pushdown(s[i]);
while(x!=k)
{
int y=tr[x].fa,z=tr[y].fa;
if(y!=k)
{
if((tr[y].ch[]==x)^(tr[z].ch[]==y))rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int fmin(int x){while(tr[x].ch[])x=tr[x].ch[];return x;}
int fmax(int x){while(tr[x].ch[])x=tr[x].ch[];return x;}
void split(int l,int r)
{
splay(l,root);int x=fmax(tr[l].ch[]);
splay(r,root);int y=fmin(tr[r].ch[]);
splay(x,root);splay(y,tr[x].ch[]);
}
void build(int l,int r,int last)
{
if(l>r)return;
int mid=(l+r)>>;
tr[q[mid]].fa=q[last];
tr[q[last]].ch[mid>last]=q[mid];
build(l,mid-,mid);build(mid+,r,mid);
pushup(q[mid]);
}
void print(int x)
{
printf("[%d] [fa]%d [v]%lld [sum]%lld [t]%d [num]%d\n",x,tr[x].fa,tr[x].v,tr[x].sum,tr[x].t,tr[x].num);
int l=tr[x].ch[],r=tr[x].ch[];
if(l)print(l);if(r)print(r);
}
void query()
{
int x=read();
splay(x+,root);
printf("%lld\n",tr[tr[x+].ch[]].sum+tr[x+].v);
}
void change()
{
int x=read(),y=read();
split(x+,x+n+);
int yi=tr[root].ch[],xi=tr[yi].ch[];
tr[yi].ch[]=;pushup(yi);pushup(root);
splay(y+,root);
int u=fmin(tr[y+].ch[]);
splay(u,tr[y+].ch[]);
tr[xi].fa=u;
tr[u].ch[]=xi;
pushup(u);pushup(root);
}
void add()
{
int x=read();long long tag=read();
split(x+,x+n+);
int yi=tr[root].ch[],xi=tr[yi].ch[];
tr[xi].tag+=tag;tr[xi].sum+=tag*tr[xi].num;tr[xi].v+=tag*tr[xi].t;
pushup(yi);pushup(root);
}
int main()
{
char str[];
n=read();
for(int i=;i<=n;i++)f=read(),insert(f,i);
for(int i=;i<=n;i++)f=read(),tr[i+].v=f,tr[i+].t=,tr[i+n+].v=-f,tr[i+n+].t=-;
cnt=;dfs();root=q[n+];
q[]=;q[*n+]=*n+;
build(,*n+,);
m=read();
while(m--)
{
scanf("%s",str);
if(str[]=='Q')query();
if(str[]=='C')change();
if(str[]=='F')add();
}
return ;
}
splay的分裂合并【Time:19964 ms】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=;
struct node{int ch[],fa,t,num;long long v,sum,tag;}tr[N<<];
struct edge{int next,to;}e[N];
int n,m,f,root,cnt;
int head[N],q[N<<],s[N<<];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
void insert(int a,int b){cnt++;e[cnt].to=b;e[cnt].next=head[a];head[a]=cnt;}
void dfs(int x)
{
q[++cnt]=x+;
for(int i=head[x];i;i=e[i].next)dfs(e[i].to);
q[++cnt]=x+n+;
}
void add(int x,long long tag){tr[x].sum+=tag*tr[x].num;tr[x].v+=tag*tr[x].t;}
void pushup(int x)
{
int l=tr[x].ch[],r=tr[x].ch[];
tr[x].num=tr[l].num+tr[r].num+tr[x].t;
tr[x].sum=tr[l].sum+tr[r].sum+tr[x].v;
}
void pushdown(int x)
{
int l=tr[x].ch[],r=tr[x].ch[];long long tag=tr[x].tag;
if(l)tr[l].tag+=tag,add(l,tag);
if(r)tr[r].tag+=tag,add(r,tag);
tr[x].tag=;
}
void rotate(int x,int& k)
{
int y=tr[x].fa,z=tr[y].fa,l,r;
if(tr[y].ch[]==x)l=;else l=;r=l^;
if(y==k)k=x;
else{if(tr[z].ch[]==y)tr[z].ch[]=x;else tr[z].ch[]=x;}
tr[x].fa=z;tr[y].fa=x;tr[tr[x].ch[r]].fa=y;
tr[y].ch[l]=tr[x].ch[r];tr[x].ch[r]=y;
pushup(y);pushup(x);
}
void splay(int x,int& k)
{
int top=;s[++top]=x;
for(int i=x;tr[i].fa;i=tr[i].fa)s[++top]=tr[i].fa;
for(int i=top;i;i--)if(tr[s[i]].tag)pushdown(s[i]);
while(x!=k)
{
int y=tr[x].fa,z=tr[y].fa;
if(y!=k)
{
if((tr[y].ch[]==x)^(tr[z].ch[]==y))rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int find(int x){while(tr[x].ch[])x=tr[x].ch[];return x;}
void build(int l,int r,int last)
{
if(l>r)return;
int mid=(l+r)>>;
tr[q[mid]].fa=q[last];
tr[q[last]].ch[mid>last]=q[mid];
build(l,mid-,mid);build(mid+,r,mid);
pushup(q[mid]);
}
int merge(int r1,int r2)
{
int w=find(r1);
splay(w,r1);
tr[w].ch[]=r2;
tr[r2].fa=w;
pushup(w);
return w;
}
void cutl(int x,int rt,int& r1,int& r2)
{
splay(x,rt);
r1=tr[x].ch[];r2=x;
tr[x].ch[]=;
tr[r1].fa=;
pushup(x);
}
void cutr(int x,int rt,int& r1,int& r2)
{
splay(x,rt);
r1=x;r2=tr[x].ch[];
tr[x].ch[]=;
tr[r2].fa=;
pushup(x);
}
void query()
{
int x=read()+;
splay(x,root);
printf("%lld\n",tr[tr[x].ch[]].sum+tr[x].v);
}
void change()
{
int x=read()+,y=x+n,k=read()+,p1,p2,p3;
cutl(x,root,p1,p2);
cutr(y,p2,p2,p3);
cutr(k,merge(p1,p3),p1,p3);
root=merge(merge(p1,p2),p3);
}
void add()
{
int x=read()+,y=x+n;long long tag=read();
splay(x,root);splay(y,tr[x].ch[]);
int z=tr[y].ch[];
add(x,tag);add(y,tag);
add(z,tag);tr[z].tag+=tag;
pushup(y);pushup(x);
}
int main()
{
char str[];
n=read();
for(int i=;i<=n;i++)f=read(),insert(f,i);
for(int i=;i<=n+;i++)f=read(),tr[i].v=f,tr[i].t=,tr[i+n].v=-f,tr[i+n].t=-;
cnt=;q[++cnt]=;dfs();q[++cnt]=*n+;
build(,*n+,);root=q[n+];
m=read();
while(m--)
{
scanf("%s",str);
if(str[]=='Q')query();
if(str[]=='C')change();
if(str[]=='F')add();
}
return ;
}