Link-Cut-Tree 模板

此模板不包含进阶的区间操作，仅实现了LCT的基础操作，关于维护更多信息的LCT请参考Splay的操作 -> [Splay 区间模板]

注意：此模板的fa指针为辅助树和原树共用，虚边保证仅连接了fa而不连接ch[]指针。

#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cassert>

#define null 0x0
#define N 200000 + 5

template <typename _Tp>
__inline void read(_Tp &a, char c = 0) {
    for (c = getchar(); !isdigit(c); c = getchar());
    for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}
int n, m, a, b;

class node {
  public:
    int fa, ch[2], rev;
    node() { ch[0] = ch[1] = fa = rev = null; }
} tr[N];

__inline void down(int u) {
    if (tr[u].rev) {
        if (tr[u].ch[0]) tr[tr[u].ch[0]].rev ^= 1;
        if (tr[u].ch[1]) tr[tr[u].ch[1]].rev ^= 1;
        tr[u].rev = 0;
        std::swap(tr[u].ch[0], tr[u].ch[1]);
    }
}

__inline int son(int u) { return tr[tr[u].fa].ch[1] == u; }
__inline int isroot(int u) { return tr[tr[u].fa].ch[0] != u && tr[tr[u].fa].ch[1] != u; }

__inline void rotate(int u) {
    int f = tr[u].fa, pf = tr[f].fa, d = son(u);
    tr[u].fa = pf;
    if (!isroot(f)) tr[pf].ch[son(f)] = u, tr[u].fa = pf;
    tr[f].ch[d] = tr[u].ch[d ^ 1];
    if (tr[f].ch[d]) tr[tr[f].ch[d]].fa = f;
    tr[f].fa = u, tr[u].ch[d ^ 1] = f;
}

int st[N];
inline void splay(int u) {
    int top = 0; st[++top] = u;
    for (int v = u; !isroot(v); v = tr[v].fa) st[++top] = tr[v].fa;
    for (int i = top; i; i--) down(st[i]);
    while (!isroot(u)) {
        if (!isroot(tr[u].fa)) rotate(son(u) == son(tr[u].fa) ? tr[u].fa : u);
        rotate(u);
    }
}
inline void access(int u, int t = 0) {
    while (u) { splay(u); tr[u].ch[1] = t; t = u, u = tr[u].fa; }
}
inline void makeroot(int u) {
    access(u);
    splay(u);
    tr[u].rev ^= 1;
}
inline void link(int u, int v) {
    makeroot(u);
    tr[u].fa = v;
    splay(u);
}
inline void cut(int u, int v) {
    makeroot(u);
    access(v);
    splay(v);
    tr[u].fa = tr[v].ch[0] = null;
}
inline int getroot(int u) {
    access(u);
    splay(u);
    while (tr[u].ch[0]) u = tr[u].ch[0];
    splay(u);
    return u;
}
inline int judge(int u, int v) {
    return getroot(u) == getroot(v);
}

int main() {
    read(n), read(m);
    while (m--) {
        char s[10]; scanf("%s", s);
        read(a), read(b);
        if (s[0] == 'Q') printf("%s\n", judge(a, b) ? "Yes" : "No");
        if (s[0] == 'C') link(a, b);
        if (s[0] == 'D') cut(a, b);
    }
    return 0;
}
Code language: PHP (php)