BZOJ 2049 SDOI2008 洞穴勘测 LCT板子

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2049

题意概述：给出N个点，一开始不连通，M次操作，删边加边，保证图是一个森林，询问两点连通性。

N<=10000,M<=200000

实际上我就是想来放个LCT板子。。。。。。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<map>

 #include<vector>

 #include<cctype>

 using namespace std;

 int N,M;

 struct link_cut_tree{

     static const int maxn=;

     struct node{

         int ch[],fa; bool res;

         node(){ ch[]=ch[]=fa=,res=; }

     }nd[maxn];

     void init(int n) { for(int i=;i<=n;i++) nd[i].ch[]=nd[i].ch[]=nd[i].fa=,nd[i].res=; }

     void link(int x,int d,int y) { nd[x].ch[d]=y,nd[y].fa=x; }

     bool isrt(int x) { return nd[nd[x].fa].ch[]!=x&&nd[nd[x].fa].ch[]!=x; }

     void pushdown(int x)

     {

         if(!nd[x].res) return;

         int lc=nd[x].ch[],rc=nd[x].ch[];

         if(lc) nd[lc].res^=,swap(nd[lc].ch[],nd[lc].ch[]);

         if(rc) nd[rc].res^=,swap(nd[rc].ch[],nd[rc].ch[]);

         nd[x].res=;

     }

     void rot(int x)

     {

         int y=nd[x].fa,z=nd[y].fa;

         pushdown(y);pushdown(x);

         if(!isrt(y)) link(z,nd[z].ch[]==y,x); nd[x].fa=z;

         int d=nd[y].ch[]==x;

         link(y,d^,nd[x].ch[d]);

         link(x,d,y);

     }

     void splay(int x)

     {

         pushdown(x);

         while(!isrt(x)){

             int y=nd[x].fa,z=nd[y].fa;

             if(!isrt(y)) rot((nd[y].ch[]==x)==(nd[z].ch[]==y)?y:x);

             rot(x);

         }

     }

     void access(int x)

     {

         int y=;

         while(x){ splay(x); nd[x].ch[]=y,y=x,x=nd[x].fa; }

     }

     void mroot(int x)

     {

         access(x); splay(x);

         nd[x].res^=,swap(nd[x].ch[],nd[x].ch[]);

     }

     void Link(int x,int y) { mroot(x); nd[x].fa=y; }

     void Cut(int x,int y)

     {

         mroot(x); access(y); splay(y);

         nd[x].fa=nd[y].ch[]=;

     }

     int find(int x)

     {

         access(x); splay(x);

         while(nd[x].ch[]){ pushdown(nd[x].ch[]); x=nd[x].ch[]; }

         return x;

     }

 }lct;

 void work()

 {

     scanf("%d%d",&N,&M);

     char op[]; int x,y;

     for(int i=;i<=M;i++){

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

         if(op[]=='C') lct.Link(x,y);

         else if(op[]=='D') lct.Cut(x,y);

         else if(op[]=='Q') puts(lct.find(x)==lct.find(y)?"Yes":"No");

     }

 }

 int main()

 {

     work();

     return ;

 }