BZOJ3282: Tree (LCT模板)

Description

给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。

操作有４种。操作从０到３编号。点从１到Ｎ编号。

０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。

保证ｘ到ｙ是联通的。

１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。

２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。

３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。

Input

第１行两个整数,分别为Ｎ和Ｍ,代表点数和操作数。

第２行到第Ｎ＋１行,每行一个整数,整数在［１,１０＾９］内,代表每个点的权值。

第Ｎ＋２行到第Ｎ＋Ｍ＋１行,每行三个整数,分别代表操作类型和操作所需的量。

１＜＝Ｎ，Ｍ＜＝３０００００

Output

对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。

Sample Input

3 3
1
2
3
1 1 2
0 1 2
0 1 1

Sample Output

3
1

解题思路：

这是LCT很好的模板。

主要难点是处理一下路径权值，和判断两个点是否联通（以防重边）

路径权值：单独将x到y的路径提取（split）Splay维护链的时候在将节点处权值上传，最后查值就好

判断有无x到y的边：将x到y的路径提取，若直接连接无中间值就是有边。

代码：

 #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]

 const int N=;

 struct trnt{

     int ch[];

     int lzt;

     int fa;

     int val;

     int sum;

     bool anc;

 }tr[N];

 int n,m;

 int cnt;

 bool whc(int spc)

 {

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

 }

 void pushup(int spc)

 {

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

     return ;

 }

 void trr(int spc)

 {

     if(!spc)

         return ;

     std::swap(lll,rrr);

     tr[spc].lzt^=;

     return ;

 }

 void pushdown(int spc)

 {

     if(tr[spc].lzt)

     {

         trr(lll);

         trr(rrr);

         tr[spc].lzt=;

     }

     return ;

 }

 void recal(int spc)

 {

     if(!tr[spc].anc)

         recal(tr[spc].fa);

     pushdown(spc);

 }

 void rotate(int spc)

 {

     int f=tr[spc].fa;

     bool k=whc(spc);

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

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

     if(tr[f].anc)

     {

         tr[f].anc=false;

         tr[spc].anc=true;

     }else

         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(f);

     pushup(spc);

 }

 void splay(int spc)

 {

     recal(spc);

     while(!tr[spc].anc)

     {

         int ft=tr[spc].fa;

         if(tr[ft].anc)

         {

             rotate(spc);

             return ;

         }

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

             rotate(spc);

         else

             rotate(ft);

         rotate(spc);

     }

     return ;

 }

 void access(int spc)

 {

     int lsts=;

     while(spc)

     {

         splay(spc);

         tr[rrr].anc=true;

         tr[lsts].anc=false;

         rrr=lsts;

         pushup(spc);

         lsts=spc;

         spc=tr[spc].fa;

     }

     return ;

 }

 void Mtr(int spc)

 {

     access(spc);

     splay(spc);

     trr(spc);

     return ;

 }

 int spmrt(int spc)

 {

     access(spc);

     splay(spc);

     while(lll)

     {

         pushdown(spc);

         spc=lll;

     }

     return spc;

 }

 void split(int x,int y)

 {

     Mtr(x);

     access(y);

     splay(y);

 }

 void Link(int x,int y)

 {

     Mtr(x);

     if(spmrt(y)!=x)

         tr[x].fa=y;

     return ;

 }

 void Cut(int x,int y)

 {

     Mtr(x);

     if(spmrt(y)==x&&tr[x].fa==y&&!tr[y].rs)

     {

         tr[x].anc=;

         tr[y].ls=;

         tr[x].fa=;

         pushup(y);

     }

     return ;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

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

     {

         scanf("%d",&tr[i].val);

         tr[i].anc=true;

     }

     while(m--)

     {

         int cmd,x,y;

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

         if(cmd==)

         {

             split(x,y);

             printf("%d\n",tr[y].sum);

         }

         if(cmd==)

             Link(x,y);

         if(cmd==)

             Cut(x,y);

         if(cmd==)

         {

             splay(x);

             tr[x].val=y;

             pushup(x);

         }

     }

     return ;

 }

巴特西