[LCT刷题] P2147 洞穴勘测

[P2147 SDOI2008] 洞穴勘测 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

非常模板的LCT维护连通性，不需要push_up操作。

可以发现，实际上LCT可以充当可撤销并查集的作用，只不过是复杂度略高。

#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 > op >> u >> v;
        if(op[0] == 'C') LCT::link(u, v);
        elif(op[0] == 'D') LCT::cut(u, v);
        else cout