【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
1
1
4 5 7
5
Q 2
F 1 3
Q 2
C 2 3
Q 2
Sample Output
15
25
HINT
n<=100000,m<=300000,1<di,xi<=n,wi,qi<=100000.保证操作合法。
题解：参考http://blog.csdn.net/PoPoQQQ/article/details/41649197
如果没有C操作，我们完全可以树剖搞定，但树剖不能实现修改子树
于是我们想到在DFS序中，先求出入栈出栈序，那么子树就变成了一段连续的区间，这样我们就可以用Splay来进行区间移动，并维护区间和
那么在入栈出栈序中怎么求出到根节点的路径上的点权和呢？
我们可以给入栈出栈序上的每个点乘以一个系数，入栈为1，出栈为-1，这样我们只要求一个前缀和就可以啦。但我们还要维护Splay中区间的系数和，因为这在区间修改时会用到
好久没写Splay了，以前写的的Splay都是直来直去的区间，今天调试时各种WA，各种TLE，各种RE，渣电脑快被我搞炸了~
还有注意这题要开long long
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100010;
typedef long long ll;
struct node
{
ll fa,ch[2],size;
ll tag,sw,sv,w,v;
}p[maxn<<1];
ll n,m,tot,cnt,root;
ll f[maxn],to[maxn],next[maxn],head[maxn],q[maxn<<1];
char str[5];
ll readin()
{
ll ret=0; char gc;
while(gc<'0'||gc>'9') gc=getchar();
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret;
}
void dfs(ll x)
{
q[++tot]=x;
for(ll i=head[x];i!=-1;i=next[i]) dfs(to[i]);
q[++tot]=x+n;
}
void add(ll a,ll b)
{
to[cnt]=b;
next[cnt]=head[a];
head[a]=cnt++;
}
void pushup(ll x)
{
p[x].sw=p[p[x].ch[0]].sw+p[p[x].ch[1]].sw+p[x].w;
p[x].sv=p[p[x].ch[0]].sv+p[p[x].ch[1]].sv+p[x].v;
p[x].size=p[p[x].ch[0]].size+p[p[x].ch[1]].size+1;
}
void pushdown(ll x)
{
if(p[x].ch[0]) p[p[x].ch[0]].sw+=p[p[x].ch[0]].sv*p[x].tag,p[p[x].ch[0]].w+=p[p[x].ch[0]].v*p[x].tag,p[p[x].ch[0]].tag+=p[x].tag;
if(p[x].ch[1]) p[p[x].ch[1]].sw+=p[p[x].ch[1]].sv*p[x].tag,p[p[x].ch[1]].w+=p[p[x].ch[1]].v*p[x].tag,p[p[x].ch[1]].tag+=p[x].tag;
p[x].tag=0;
}
void build(ll l,ll r,ll last)
{
if(l>r) return ;
ll mid=l+r>>1;
p[q[mid]].fa=q[last];
if(last) p[q[last]].ch[mid>last]=q[mid];
build(l,mid-1,mid),build(mid+1,r,mid);
pushup(q[mid]);
}
void rotate(ll x,ll &k)
{
ll y=p[x].fa,z=p[y].fa,d=(x==p[y].ch[1]);
if(y==k) k=x;
else p[z].ch[y==p[z].ch[1]]=x;
p[x].fa=z,p[y].fa=x,p[y].ch[d]=p[x].ch[d^1];
if(p[x].ch[d^1]) p[p[x].ch[d^1]].fa=y;
p[x].ch[d^1]=y;
pushup(y),pushup(x);
}
ll qrank(ll x)
{
ll ret;
if(x==root) ret=p[p[x].ch[0]].size+1;
else if(x==p[p[x].fa].ch[0]) ret=qrank(p[x].fa)-p[p[x].ch[1]].size-1;
else ret=qrank(p[x].fa)+p[p[x].ch[0]].size+1;
pushdown(x);
return ret;
}
void splay(ll x,ll &k)
{
while(x!=k)
{
ll y=p[x].fa,z=p[y].fa;
if(y!=k)
{
if((p[y].ch[0]==x)^(p[z].ch[0]==y)) rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
ll find(ll x,ll y)
{
pushdown(x);
if(p[p[x].ch[0]].size+1==y) return x;
if(y<=p[p[x].ch[0]].size) return find(p[x].ch[0],y);
else return find(p[x].ch[1],y-p[p[x].ch[0]].size-1);
}
void _Q()
{
ll x;
x=readin();
qrank(x);
splay(x,root);
printf("%lld
",p[p[x].ch[0]].sw+p[x].w);
}
void _C()
{
ll x,y,u,t;
x=readin(),y=readin();
splay(find(root,qrank(x)-1),root);
splay(find(root,qrank(x+n)+1),p[root].ch[1]);
u=p[p[root].ch[1]].ch[0];
p[p[root].ch[1]].ch[0]=0;
pushup(p[root].ch[1]),pushup(root);
qrank(y),qrank(y+n);
splay(y,root);
splay(y+n,p[root].ch[1]);
t=p[root].ch[1];
while(p[t].ch[0]) t=p[t].ch[0];
qrank(t);
p[t].ch[0]=u,p[u].fa=t;
while(t) pushup(t),t=p[t].fa;
}
void _F()
{
ll x,y;
x=readin(),y=readin();
splay(find(root,qrank(x)-1),root);
splay(find(root,qrank(x+n)+1),p[root].ch[1]);
p[p[p[root].ch[1]].ch[0]].sw+=p[p[p[root].ch[1]].ch[0]].sv*y;
p[p[p[root].ch[1]].ch[0]].w+=p[p[p[root].ch[1]].ch[0]].v*y;
p[p[p[root].ch[1]].ch[0]].tag+=y;
}
int main()
{
n=readin();
ll i;
memset(head,-1,sizeof(head));
for(i=2;i<=n;i++) f[i]=readin(),add(f[i],i);
for(i=1;i<=n;i++) p[i].w=readin(),p[i+n].w=-p[i].w,p[i].v=1,p[i+n].v=-1;
tot=1;
dfs(1);
root=q[n+1],q[1]=2*n+1,q[2*n+2]=2*n+2;
build(1,2*n+2,0);
m=readin();
for(i=1;i<=m;i++)
{
scanf("%s",str);
switch(str[0])
{
case 'Q':_Q(); break;
case 'C':_C(); break;
case 'F':_F(); break;
}
}
return 0;
}