LCT(洞穴勘测)

codevs洞穴勘测原题戳这里
题目大意:
建路 Connect u v
毁路 Destroy u v
查询路是否联通 Query u v

用到的几个基本操作，link，cut，access，reverse，find

/*本题中所用到的ch和fa，为splay树上的，与原树没有关系*/
/*博主个人爱好结构体，不适者可自动yy成数组*/
#include
#include
#include
#include
using namespace std; 

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int n,m;
int st[10050];

struct LCT{
    int ch[2];
    int fa,rev;
}t[10050];

int isroot(int x)
{
    return t[t[x].fa].ch[0]!=x&&t[t[x].fa].ch[1]!=x;

}

void pushdown(int k)
{
    int l=t[k].ch[0],r=t[k].ch[1];
    if(t[k].rev)
    {
        t[k].rev^=1;
        t[l].rev^=1;
        t[r].rev^=1;
        swap(t[k].ch[0],t[k].ch[1]);
    }
}

void rotate(int x)
{
     int y=t[x].fa,z=t[y].fa,l,r;
     if(t[y].ch[0]==x)l=0;
     else l=1;
     r=l^1;
     if(!isroot(y))//如果y不是splay树的树根 
     {
        if(t[z].ch[0]==y)t[z].ch[0]=x; 
        else t[z].ch[1]=x;
     }
     t[x].fa=z;
     t[y].fa=x;
     t[t[x].ch[r]].fa=y;
     t[y].ch[l]=t[x].ch[r];
     t[x].ch[r]=y;
}
//一些被注释掉的部分为正常的splay,博主手残试了下，不适用于本题，会全T
//bool son(int x)
//{
//    return t[t[x].fa].ch[1]==x;//rc:1,lc:0
//}
//
//void point(int x,int fa,bool z)
//{
//  if(x)t[x].fa=fa;
//  if(fa)t[fa].ch[z]=x;
//  //else root=x;
//}
//
//void rotate(int x)
//{
//  int y=t[x].fa;
//  int z=t[y].fa;
//  bool yy=son(y),xx=son(x);
//  point(t[x].ch[!xx],y,xx);
//  point(y,x,!xx);
//  point(x,z,yy);
////    rejs(y);
////    rejs(x);
//}

void splay(int x)
{
    int top=0;
    st[++top]=x;
    for(int i=x;!isroot(i);i=t[i].fa)
    {
        st[++top]=t[i].fa;
    }
    for(int i=top;i;i--)pushdown(st[i]);
    while(!isroot(x))
    {
        int y=t[x].fa,z=t[y].fa;
        if(!isroot(y))
        {
            if(t[y].ch[0]==x^t[z].ch[0]==y)rotate(x);//优先级！！！！！！！ 
            else 
            rotate(y);
        }
        rotate(x);
    }
}

void access(int x)
{
    int l=0;
    while(x)
    { 
        splay(x);
        t[x].ch[1]=l;
        l=x;
        x=t[x].fa;
    }
}

void rever(int x)
{
    access(x);
    splay(x);
    t[x].rev^=1;
}

void link(int x,int y)
{
    rever(x);
    t[x].fa=y;
    splay(x);
}

void cut(int x,int y)
{
    rever(x);
    access(y);
    splay(y);
    t[y].ch[0]=t[x].fa=0;
}

int find(int x)
{
    access(x);
    splay(x);
    int y=x;
    while(t[y].ch[0])y=t[y].ch[0];
    return y;
}

int main()
{
    char ch[10];
    int x,y;
//  scanf("%d%d",&n,&m);
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        scanf("%s",ch);
//      scanf("%d%d",&x,&y);
        x=read(),y=read();
        if(ch[0]=='C')link(x,y);
        else if(ch[0]=='D')cut(x,y);
        else
        {
            if(find(x)==find(y))printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}