Cogs2701.动态树（使用LCT维护子树信息）

本文讨论了在处理动态树问题时，如何利用链剖分（Link-Cut Tree, LCT）来高效维护和查询子树信息。LCT 是一种高级数据结构，能够支持树的动态修改操作，如链接（link）、切割（cut）以及路径查询等。

以下是使用 C++ 实现的一个示例代码，展示了如何通过 LCT 来维护子树的大小信息：

#include 
#include 
using namespace std;
const int N = 2e5 + 5;
int f[N], ch[N][2], st[N], tag[N];
int sum[N], sz[N]; // sum: 当前节点在 Splay 中左子树节点数 + 右子树节点数 + 虚子树信息 + 1 (自身)

inline void pushup(int x) {
    sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + sz[x] + 1; // 更新当前节点的信息
}

inline void pushdown(int x) {
    if (!tag[x]) return;
    swap(ch[ch[x][0]][0], ch[ch[x][0]][1]);
    tag[ch[x][0]] ^= 1;
    swap(ch[ch[x][1]][0], ch[ch[x][1]][1]);
    tag[ch[x][1]] ^= 1;
    tag[x] = 0;
}

inline bool notroot(int x) { // 判断是否为当前 Splay 的根
    return ch[f[x]][0] == x || ch[f[x]][1] == x;
}

inline void rotate(int x) {
    int y = f[x], z = f[y], w = (ch[y][1] == x);
    if (notroot(y)) ch[z][ch[z][1] == y] = x;
    f[x] = z;
    ch[y][w] = ch[x][w ^ 1];
    if (ch[y][w]) f[ch[y][w]] = y;
    ch[x][w ^ 1] = y, f[y] = x;
    pushup(y), pushup(x);
}

inline void splay(int x) {
    int y = x, num = 0;
    st[++num] = y;
    while (notroot(y)) st[++num] = (y = f[y]);
    while (num) pushdown(st[num--]);
    if (!notroot(x)) return;
    for (int fa = f[x]; notroot(x); rotate(x), fa = f[x])
        if (notroot(fa)) ((ch[fa][1] == x) ^ (ch[f[fa]][1] == fa)) ? rotate(x) : rotate(fa);
}

inline void access(int x) {
    for (int y = 0; x; x = f[y = x]) {
        splay(x);
        sz[x] += sum[ch[x][1]] - sum[y];
        ch[x][1] = y;
        pushup(x); // 更新 sz[x]
    }
}

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

inline int findroot(int x) {
    access(x), splay(x);
    while (ch[x][0]) pushdown(x), x = ch[x][0];
    splay(x);
    return x;
}

inline void link(int x, int y) {
    makeroot(x), makeroot(y);
    f[y] = x;
    sz[x] += sum[y];
    pushup(x); // 确保 x 和 y 都是根节点
}

int main() {
    int n, m, typ, u, v;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) sum[i] = 1;
    while (m--) {
        scanf("%d%d", &typ, &u);
        if (typ == 1) makeroot(u);
        if (typ == 2) access(u), printf("%d\n", sz[u] + 1); // 输出子树大小
        if (typ == 3) {
            scanf("%d", &v);
            int root = findroot(u);
            link(u, v);
            makeroot(root);
        }
    }
    return 0;
}