BZOJ 2049: [Sdoi2008]Cave 洞穴勘测 LCT

//qscqesze
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 200006
#define mod 1000000007
#define eps 1e-9
#define e exp(1.0)
#define PI acos(-1)
#define lowbit(x) (x)&(-x)
const double EP  = 1E-10 ;
int Num;
//const int inf=0x7fffffff;
const ll inf=999999999;
inline ll read()
{
    ll 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;
}
//*************************************************************************************

const int MAXN = 100010;
struct Node {
    Node *ch[2], *p; int size, value;
    bool rev;
    Node(int t = 0);
    inline bool dir(void) {return p->ch[1] == this;}
    inline void SetC(Node *x, bool d) {
        ch[d] = x; x->p = this;
    }
    inline void Rev(void) {
        swap(ch[0], ch[1]); rev ^= 1;
    }
    inline void Push(void) {
        if (rev) {
            ch[0]->Rev();
            ch[1]->Rev();
            rev = 0;
        }
    }
    inline void Update(void) {
        size = ch[0]->size + ch[1]->size + 1;
    }
}Tnull, *null = &Tnull, *fim[MAXN];
// 要记得额外更新null的信息
Node::Node(int _value){ch[0] = ch[1] = p = null; rev = 0;}
inline bool isRoot(Node *x) {return x->p == null || (x != x->p->ch[0] && x != x->p->ch[1]);}
inline void rotate(Node *x) {
    Node *p = x->p; bool d = x->dir();
    p->Push(); x->Push();
    if (!isRoot(p)) p->p->SetC(x, p->dir()); else x->p = p->p;
    p->SetC(x->ch[!d], d);
    x->SetC(p, !d);
    p->Update();
}
inline void splay(Node *x) {
    x->Push();
    while (!isRoot(x)) {
        if (isRoot(x->p)) rotate(x);
        else {
            if (x->dir() == x->p->dir()) {rotate(x->p); rotate(x);}
            else {rotate(x); rotate(x);}
        }
    }
    x->Update();
}
inline Node* Access(Node *x) {
    Node *t = x, *q = null;
    for (; x != null; x = x->p) {
        splay(x); x->ch[1] = q; q = x;
    }
    splay(t); //info will be updated in the splay;
    return q;
}
inline void Evert(Node *x) {
    Access(x); x->Rev();
}
inline void link(Node *x, Node *y) {
    Evert(x); x->p = y;
}
inline Node* getRoot(Node *x) {
    Node *tmp = x;
    Access(x);
    while (tmp->Push(), tmp->ch[0] != null) tmp = tmp->ch[0];
    splay(tmp);
    return tmp;
}
// 一定要确定x和y之间有边
inline void cut(Node *x, Node *y) {
    Access(x); splay(y);
    if (y->p != x) swap(x, y);
    Access(x); splay(y);
    y->p = null;
}
inline Node* getPath(Node *x, Node *y) {
    Evert(x); Access(y);
    return y;
}
inline void clear(void) {
    null->rev = 0; null->size = 0; null->value = 0;
}

int judge(Node *x,Node *y)
{
    while(x->p!=null)x = x->p;
    while(y->p!=null)y = y->p;
    if(x!=y)return 0;
    return 1;
}
int main()
{
    clear();
    int n=read(),m=read();
    for(int i=1;i<=n;i++)
        fim[i] = new Node();
    char c[25];
    int u,v;
    while(m--)
    {
        scanf("%s%d%d",c,&u,&v);
        if(c[0]==‘Q‘)
        {
            if(judge(fim[u],fim[v]))
                printf("Yes\n");
            else
                printf("No\n");
        }
        else if(c[0]==‘C‘)
            link(fim[u],fim[v]);
        else
            cut(fim[u],fim[v]);
    }
}