bzoj3786星系探索(splay维护dfs序)

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

Sample Output

9
15
25

解题思路：

这道题假如没有换根操作，那么就是一入栈出栈序的裸题，也就是，对于子树更改节点，在入栈出栈序上这个点入栈处加入操作，在出栈处取消操作（区间加和就好）。而查询操作，则是查询某个点入栈序的前缀和。验证这个方法的正确性：如果这个点i是点j的子树中的点，那么就能查询到加入操作，而查询不到取消操作。那么就是说，如果查询前缀时，若同时查询到了入栈和出栈，那么操作就会被取消。

对于这道题，区间和可以被认为是子树权值和，只要子树中同时有入栈和出栈，那么权值上就没有这个点。

那么就维护一下入栈出栈序。

用splay维护入栈出栈序，splay的中序遍历就是入栈出栈序。

考虑操作Q，查询入栈出栈序的前缀和。

那么就是将这个点的入栈位置旋转到根，答案就是左子树权值和+根权。

考虑操作C，将一段入栈出栈序插入到另一段入栈出栈序之中。

那么就先将这段入栈出栈序的前驱旋转到根，再将后继旋转至根的儿子。

那么我们就将这棵树像挤痘痘一样挤了出来。

然后将根摘除并pushup两次愈合伤口。

再旋转出要加的位置栽上，再pushup两次使其无缝连接^_^

考虑操作F，将子树加权。

懒惰标记旋转时下传即可。

注意：

1.由于入栈出栈序一一对应，取消操作只要是加入操作的相反数即可。

2.子树内求和懒惰标记时总和为入栈个数。

代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define lll tr[spc].ch[0]

 #define rrr tr[spc].ch[1]

 #define ls ch[0]

 #define rs ch[1]

 typedef long long lnt;

 const int N=;

 struct pnt{

     int hd;

     int ind;

     int oud;

     lnt vl;

 }p[N];

 struct ent{

     int twd;

     int lst;

 }e[N];

 struct trnt{

     int ch[];

     int fa;

     lnt val;

     lnt sum;

     lnt wgt;

     lnt ctr;

     lnt lzt;

     lnt fst;

     lnt chr;

 }tr[N],stdtr;

 int n,m,cnt,siz;

 int root;

 int ic;

 int plc[N];

 int dnf[N];

 char cmd[];

 int vls(int x)

 {

     if(x==||x==ic+)

         return ;

     return (p[dnf[x]].ind==x)?:-;

 }

 bool whc(int spc)

 {

     return tr[tr[spc].fa].rs==spc;

 }

 void new_point(int spc,int i)

 {

     tr[spc]=stdtr;

     int cmdlp=vls(i);

     plc[i]=spc;

     tr[spc].chr=dnf[i];

     tr[spc].val=p[dnf[i]].vl*cmdlp;

     tr[spc].ctr=cmdlp;

     return ;

 }

 void ade(int f,int t)

 {

     cnt++;

     e[cnt].twd=t;

     e[cnt].lst=p[f].hd;

     p[f].hd=cnt;

     return ;

 }

 void dfs(int x)

 {

     p[x].ind=++ic;

     dnf[ic]=x;

     for(int i=p[x].hd;i;i=e[i].lst)

         dfs(e[i].twd);

     p[x].oud=++ic;

     dnf[ic]=x;

     return ;

 }

 void pushup(int spc)

 {

     tr[spc].wgt=tr[lll].wgt+tr[rrr].wgt+;

     tr[spc].sum=tr[lll].sum+tr[rrr].sum+tr[spc].val;

     tr[spc].fst=tr[lll].fst+tr[rrr].fst+tr[spc].ctr;

     return ;

 }

 void FFT(lnt spc,lnt k)

 {

     if(!spc)

         return ;

     tr[spc].lzt+=k;

     tr[spc].sum+=k*tr[spc].fst;

     tr[spc].val+=k*tr[spc].ctr;

     return ;

 }

 void pushdown(int spc)

 {

     if(tr[spc].lzt)

     {

         FFT(lll,tr[spc].lzt);

         FFT(rrr,tr[spc].lzt);

         tr[spc].lzt=;

     }

     return ;

 }

 void build(int l,int r,int &spc,int f)

 {

     if(l>r)

         return ;

     int mid=(l+r)>>;

     spc=++siz;

     new_point(spc,mid);

     tr[spc].fa=f;

     build(l,mid-,lll,spc);

     build(mid+,r,rrr,spc);

     pushup(spc);

     return ;

 }

 void rotate(int spc)

 {

     int f=tr[spc].fa;

     pushdown(f);

     pushdown(spc);

     bool k=whc(spc);

     tr[f].ch[k]=tr[spc].ch[!k];

     tr[spc].ch[!k]=f;

     tr[tr[f].fa].ch[whc(f)]=spc;

     tr[spc].fa=tr[f].fa;

     tr[f].fa=spc;

     tr[tr[f].ch[k]].fa=f;

     pushup(spc);

     pushup(f);

     return ;

 }

 void splay(int spc,int f)

 {

     while(tr[spc].fa!=f)

     {

         int ft=tr[spc].fa;

         if(tr[ft].fa==f)

         {

             rotate(spc);

             break;

         }

         if(whc(ft)^whc(spc))

             rotate(spc);

         else

             rotate(ft);

         rotate(spc);

     }

     if(!f)

         root=spc;

     return ;

 }

 int place(int spc,int cmd)//0 qianqu

 {

     if(tr[spc].ch[cmd])

     {

         spc=tr[spc].ch[cmd];

         while(tr[spc].ch[-cmd])

             spc=tr[spc].ch[-cmd];

         return spc;

     }

     while(whc(spc)==(bool)cmd)

         spc=tr[spc].fa;

     return tr[spc].fa;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         int x;

         scanf("%d",&x);

         ade(x,i);

     }

     for(int i=;i<=n;i++)

         scanf("%lld",&p[i].vl);

     scanf("%d",&m);

     dfs();

     build(,ic+,root,);

     while(m--)

     {

         scanf("%s",cmd);

         if(cmd[]=='Q')

         {

             int x;

             scanf("%d",&x);

             splay(plc[p[x].ind],);

             printf("%lld\n",tr[root].val+tr[tr[root].ls].sum);

         }else if(cmd[]=='C')

         {

             int x,y;

             scanf("%d%d",&x,&y);

             splay(place(plc[p[x].ind],),);

             splay(place(plc[p[x].oud],),root);

             int tmp=tr[tr[root].rs].ls;

             tr[tr[root].rs].ls=;

             pushup(tr[root].rs);

             pushup(root);

             splay(plc[p[y].ind],);

             splay(place(plc[p[y].ind],),root);

             tr[tr[root].rs].ls=tmp;

             tr[tmp].fa=tr[root].rs;

             pushup(tr[root].rs);

             pushup(root);

         }else

         {

             lnt x,y;

             scanf("%lld%lld",&x,&y);

             splay(place(plc[p[x].ind],),);

             splay(place(plc[p[x].oud],),root);

             int spc=tr[tr[root].rs].ls;

             tr[spc].lzt+=y;

             tr[spc].sum+=tr[spc].fst*y;

             tr[spc].val+=tr[spc].ctr*y;

         }

     }

     return ;

 }

巴特西