[LCT刷题][连通性维护] P2147 洞穴勘测

#include 
#define elif else if
#define int long long
#define endl '\n'
using namespace std;

const int N = 4e5 + 10;

namespace LCT{
    #define ls ch[rt][0]
    #define rs ch[rt][1]
    #define std_tag 0ll

    int ch[N][2], f[N], tag[N];

    inline void push(int x) { swap(ch[x][0], ch[x][1]), tag[x] ^= 1; }

    inline void push_down(int rt) {
        if(tag[rt]){
            if(ch[rt][0]) push(ch[rt][0]);
            if(ch[rt][1]) push(ch[rt][1]);
            tag[rt] = 0; 
        } 
    }

    #define get(x) (ch[f[x]][1] == x)
    #define isRoot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x)

    inline void rotate(int x) { 
        int y = f[x], z = f[y], k = get(x);
        if(!isRoot(y)) ch[z][ch[z][1] == y] = x;
        ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;
        ch[x][!k] = y, f[y] = x, f[x] = z;
    }

    inline void update(int x) { 
        if(!isRoot(x)) update(f[x]);
        push_down(x);
    }

    inline void splay(int x) { 
        update(x);
        for(int fa = f[x]; !isRoot(x); rotate(x), fa = f[x]){
            if(!isRoot(fa)) rotate(get(fa) == get(x) ? fa : x);
        }
    }

    int access(int x) { 
        int p;
        for(p = 0; x; x = f[p = x]) splay(x), ch[x][1] = p;
        return p;
    }

    void makeRoot(int p) { access(p), splay(p), push(p); } 

    int findRoot(int x) { 
        access(x), splay(x);
        while(ch[x][0]) push_down(x), x = ch[x][0];
        splay(x);
        return x;
    }

    void link(int x, int y) { 
        makeRoot(x);
        if(findRoot(y) != x) f[x] = y;
    }
    
    void split(int x, int y) { 
        makeRoot(x);
        access(y), splay(y);
    }

    void cut(int x, int y){ 
        makeRoot(x);
        if(findRoot(y) == x && f[y] == x && !ch[y][0]){
            f[y] = ch[x][1] = 0;
        }
    }
}

inline void solve(){
    int n = 0, m = 0; cin >> n >> m;
    for(int i = 1; i <= m; i++){
        string op; int u, v;
        cin >> op >> u >> v;
        if(op[0] == 'C') LCT::link(u, v);
        elif(op[0] == 'D') LCT::cut(u, v);
        else cout << (LCT::findRoot(u) == LCT::findRoot(v) ? "Yes" : "No") << endl; 
    }   
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}