[关闭]
@zzzc18 2017-06-21T06:59:06.000000Z 字数 2371 阅读 1715

Link-Cut-Tree

LCT

讲解1
讲解2

题目：洛谷模板题

  1. #include<cstdio>
  2. #include<algorithm>
  3. #define MAXN 300005
  4. using namespace std;
  6. int n,m;
  8. class Link_Cut_Tree{
  9.     public:
  10.         struct T_T{
  11.             int lazy,ls,rs,fa,val;
  12.         };
  14.         bool isroot(int x){
  15.             return !(tree[tree[x].fa].ls==x||tree[tree[x].fa].rs==x);
  16.         }
  18.         void pushdown(int x){
  19.             if(tree[x].lazy){
  20.                 tree[x].lazy=0;
  21.                 tree[tree[x].ls].lazy^=1;
  22.                 tree[tree[x].rs].lazy^=1;
  23.                 swap(tree[x].ls,tree[x].rs);
  24.             }
  25.         }
  27.         void clean(){
  28.             tree[0].ls=tree[0].rs=tree[0].val=tree[0].lazy=0;
  29.         }
  31.         void rotate(int x){
  32.             int y=tree[x].fa,z=tree[y].fa;
  33.             if(tree[tree[y].fa].ls==y || tree[tree[y].fa].rs==y){
  34.                 if(tree[z].ls==y)
  35.                     tree[z].ls=x;
  36.                 else
  37.                     tree[z].rs=x;
  38.             }
  39.             tree[x].fa=z;
  40.             tree[y].fa=x;
  41.             if(tree[y].ls==x){
  42.                 tree[tree[x].rs].fa=y;
  43.                 tree[y].ls=tree[x].rs;
  44.                 tree[x].rs=y;
  45.             }
  46.             else{
  47.                 tree[tree[x].ls].fa=y;
  48.                 tree[y].rs=tree[x].ls;
  49.                 tree[x].ls=y;
  50.             }
  51.             up(y);up(x);
  52.             clean();
  53.         }           
  55.         int que[MAXN];
  57.         void splay(int x){
  58.             int y,z;int top=1;
  59.             que[top]=x;
  60.             for(int i=x;!isroot(i);i=tree[i].fa)
  61.                 que[++top]=tree[i].fa;
  62.             for(int i=top;i;i--)
  63.                 pushdown(que[i]);
  64.             while(tree[tree[x].fa].ls==x||tree[tree[x].fa].rs==x){
  65.                 y=tree[x].fa;z=tree[y].fa;
  66.                 if(tree[tree[y].fa].ls==y||tree[tree[y].fa].rs==y){
  67.                     if((tree[y].ls==x && tree[z].rs==y)||(tree[y].rs==x && tree[z].ls==y))
  68.                         rotate(x);
  69.                     else
  70.                         rotate(y);
  71.                 }
  72.                 rotate(x);
  73.             }
  74.         }
  76.         T_T tree[MAXN];
  77.         //////////////////////////////////////////////////////////////////////////////////////////
  78.         int xr[MAXN];
  79.         void up(int x){
  80.             xr[x]=xr[tree[x].ls]^xr[tree[x].rs]^tree[x].val;
  81.         }
  83.         void access(int x){
  84.             int t=0;
  85.             while(x){
  86.                 splay(x);
  87.                 tree[x].rs=t;
  88.                 up(x);
  89.                 t=x;
  90.                 x=tree[x].fa;
  91.             }
  92.         }
  94.         void makeroot(int x){
  95.             access(x);
  96.             splay(x);
  97.             tree[x].lazy^=1;
  98.         }
  100.         int F(int x){
  101.             access(x);
  102.             splay(x);
  103.             while(tree[x].ls)
  104.                 x=tree[x].ls;
  105.             return x;
  106.         }
  108.         void spilt(int x,int y){
  109.             makeroot(x);
  110.             access(y);
  111.             splay(y);
  112.         }
  114.         void cut(int x,int y){
  115.             spilt(x,y);
  116.             if(tree[y].ls==x){
  117.                 tree[y].ls=0;
  118.                 tree[x].fa=0;
  119.             }
  120.         }
  122.         void link(int x,int y){
  123.             makeroot(x);
  124.             tree[x].fa=y;
  125.         }
  127.         void DEBUG(){
  128.             int k;
  129.             for(k=1;k<=n;k++){
  130.                 printf("No. %2d:val=%d|ls=%d|rs=%d|fa=%d|\n",k,tree[k].val,tree[k].ls,tree[k].rs,tree[k].fa);
  131.             }
  132.         }
  133. }LCT;
  135. int main(){
  136.     freopen("LCT.in","r",stdin);
  137.     freopen("my.out","w",stdout);
  138.     scanf("%d%d",&n,&m);
  139.     int i;
  140.     for(i=1;i<=n;i++){
  141.         scanf("%d",&LCT.xr[i]);
  142.         LCT.tree[i].val=LCT.xr[i];
  143.     }
  144.     for(i=1;i<=m;i++){
  145.         int opt,x,y;
  146.         scanf("%d",&opt);
  147.         scanf("%d%d",&x,&y);
  148.         if(opt==0){
  149.             LCT.spilt(x,y);
  150.             printf("%d\n",LCT.xr[y]);
  151.         }
  152.         if(opt==1){
  153.             int xx=LCT.F(x),yy=LCT.F(y);
  154.             //printf("%d %d\n",xx,yy);
  155.             if(xx!=yy)
  156.                 LCT.link(x,y);
  157.         }
  158.         if(opt==2){
  159.             int xx=LCT.F(x),yy=LCT.F(y);
  160.             if(xx==yy)
  161.                 LCT.cut(x,y);
  162.         }
  163.         if(opt==3){
  164.             LCT.access(x);
  165.             LCT.splay(x);
  166.             LCT.tree[x].val=y;
  167.             LCT.up(x);
  168.         }
  169.         //if(i%500==0)
  170.             //LCT.DEBUG();
  171.     }
  172.     return 0;
  173. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注