LCT——Link Cut Tree

胡扯

\(LCT\) 运用实链剖分，对于一个父亲来说，只有一个儿子对应实边，其它的对应虚边，一堆的实边连在一起就变成了实链，我们用 \(Splay\) 维护。

其中实边指的是一条连通父亲儿子的双向边，而虚边则指的是儿子到父亲的单向边。在 \(LCT\) 中，实边组成的实链被 \(Splay\) 储存，而虚边则是 \(Splay\) 的根节点连到父亲的边，所以 \(LCT\) 其实可以看做一堆 \(Splay\) 通过虚边相连。

性质：

任何结点包含且仅包含于一个 \(Splay\) 中
\(Splay\) 中的结点的深度在原树中按中序遍历递增

注意 \(LCT\) 维护的是森林。

)

接下来讲 \(LCT\) 的基本操作。

Access

最重要的操作，将 \(x\) 到树根结点之间拉一条实链，以下记 \(y\) 为上一次操作的 \(Splay\) 的根，\(y\) 初始为 \(0\)。

首先我们把 \(x\) 转到它所处的 \(Splay\) 的根，然后把它的右儿子（\(y\) 深度大，由操作二替换到右儿子）改为 \(y\)，然后 \(pushup\) 一下 \(x\)，最后令 \(x = fa[x]\)。

这样子起到了什么效果呢？显然原来的右实儿子变成了虚儿子，而右儿子的地方被替换为了上一个 \(Splay\) 的根，并且连的是实边。我们的目标是将最初的 \(x\) 与根结点之间打通实链，那么 \(Access\) 的过程相当于在不断地将两个 \(Splay\) 连接起来，形成实链。

放几个图：

先是 \(Splay(N)\)

然后 \(Splay(I)\)

然后 \(Splay(H)\)

最后 \(Splay(A)\)

如此 \(A-N\) 的路径便在一个 \(Splay\) 里了。

inline void access(int x) {
    for (int y = 0; x; y = x, x = tr[x].p) 
        splay(x), tr[x].s[1] = y, pushup(x); 
}

Makeroot

将 \(LCT\) 的根换为 \(x\)。

首先 \(access(x)\)，然后 \(splay(x)\)，最后翻转一整棵 \(Splay\)。

由于 \(access\) 一直是往右儿子挂，所以最后 \(x\) 会在整棵 \(Splay\) 的最右下（即中序遍历最后的点）。所以 \(splay\) 后 \(x\) 没有右儿子，这时再将整棵 \(Splay\) 翻转，这样 \(x\) 的左子树就去了右边，\(x\) 就成了深度最小的点。

inline void reverse(int x) {
    swap(tr[x].s[0], tr[x].s[1]);
    tr[x].flag ^= 1;
}
inline void makeroot(int x) {
    access(x); splay(x); pushdown(x);
}

代码中的 \(pushdown\) 就是文艺平衡树中的懒标记下传。

Findroot

找 \(x\) 所在树的根节点。

同样 \(access(x)\)，然后 \(splay(x)\)，接着找到最左边的，它就是 \(x\) 所在树的根节点。

为了防止卡链，最后还要再 \(splay(根)\)。

inline void pushdown(int x) {
    if (tr[x].flag) {
        if (tr[x].s[0]) reverse(tr[x].s[0]);
        if (tr[x].s[1]) reverse(tr[x].s[1]);
    }
    tr[x].flag = 0; // 这里一定是等于 0，不能 ^1
}
inline int findroot(int x) {
    access(x); splay(x);
    while (tr[x].s[0]) {
        pushdown(x); // 记得下传懒标记
        x = tr[x].s[0];
    }
    splay(x);
    return x;
}

Link

将 \(x\) 和 \(y\) 连边。

首先 \(makeroot(x)\)，然后判断一下 \(findroot(y)\) 如果等于 \(x\)就不连，否则将 \(x\) 的父亲置为 \(y\) 连一条虚边。

\(findroot(y) = x\) 时不连是因为如果别人已经在一条链上了，你再连就会出现双向边或环。

inline void link(int x, int y) {
    makeroot(x);
    if (findroot(y) == x) return;
    tr[x].p = y;
}

Cut

砍掉 \(x-y\) 的边。

首先还是 \(makeroot(x)\)，接着考虑什么时候连边不合法。明显当 \(findroot(y) != x\) 时不合法，说明两者不在一棵 \(Splay\) 中。那在同一棵树中的情况呢？

你想，\(Splay\) 维护的是中序遍历，并且我们已经使 \(x\) 成为了根，所以如果 \(y\) 还有左子结点，则二者一定在原树上不相邻。同时，我们在 \(findroot\) 中已经 \(access(y)\)，所以如果 \(x\) 与 \(y\) 在同一 \(Splay\) 中却还没有连边，这条路径上一定还会有其它的点，所以如果 \(fa[y] != x\) 也是不合法的。

判完后令 \(x\) 的右儿子和 \(y\) 的父亲置为 \(NULL\)。

最后因为记得 \(pushdown\)。

为什么 \(link\) 不需要 \(pushdown\)？因为它连的是虚边。

inline void cut(int x, int y) {
    makeroot(x);
    if (findroot(y) != x || tr[y].p != x || tr[y].s[0]) return;
    tr[x].s[1] = tr[y].p = 0;
    pushup(x);
}

一个很重要的点：在使用 \(cut\) 时无论边是否一定合法都不能直接去掉判断行，因为 \(findroot\) 操作会对 \(y\) 进行操作，去掉答案会发生错误！！！！

Split

把 \(x-y\) 拆成一棵方便操作的 \(Splay\)。

因为 \(Access(y)\) 会使得 \(y\) 到根节点拉出一条实链，所以只要事先 \(makeroot(x)\) 就可以拉出一条 \(x-y\) 的实链。

最后为了方便瞎搞，可以 \(splay(y)\) 把 \(y\) 转到根节点，原因是这样子 \(y\) 只有左儿子。

inline void split(int x, int y) {
    makeroot(x); access(y); splay(y);
}

Splay

由于 \(LCT\) 引入了虚实边的概念，所以 \(Splay\) 的代码也要稍加变化。

在 \(rotate\) 中，由于 \(y\) 可能是 \(Splay\) 的根，这样 \(y-z\) 就是虚边了，所以旋转时 \(x-z\) 只能单向连边。

在 \(splay\) 中，由于每次都是转到根，\(splay\) 中就只传入一个变量，循环的判断条件也要改变。

inline void rotate(int x) {
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[x].p = z;
    if (ntroot(y)) tr[z].s[tr[z].s[1] == y] = x; 
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[y].p = x, tr[x].s[k ^ 1] = y;
    pushup(y); pushup(x);   
}

inline void splay(int x) {
    pushall(x);
    while (ntroot(x)) {
        int y = tr[x].p, z = tr[y].p;
        if (ntroot(y)) {
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}

模板

瞎扯了那么多，现在放个模板。

// 洛谷 P3690
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define initrand srand((unsigned)time(0))
#define random(x) ((LL)rand() * rand() % (x))
#define eb emplace_back
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
inline int read() {
    int 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 << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

const int N = 100010;
int n, m;

struct Splay {
    int s[2], p, val, res, flag;
} tr[N];

inline bool ntroot(int x) {
    return tr[tr[x].p].s[0] == x || tr[tr[x].p].s[1] == x;    
}

inline void reverse(int x) {
    swap(tr[x].s[0], tr[x].s[1]);
    tr[x].flag ^= 1;
}

inline void pushdown(int x) {
    if (tr[x].flag) {
        if (tr[x].s[0]) reverse(tr[x].s[0]);
        if (tr[x].s[1]) reverse(tr[x].s[1]);
    }
    tr[x].flag = 0;
}

inline void pushall(int x) {
    if (ntroot(x)) pushall(tr[x].p);
    pushdown(x);
}

inline void pushup(int x) {
    tr[x].res = tr[tr[x].s[0]].res ^ tr[tr[x].s[1]].res ^ tr[x].val;
}

inline void rotate(int x) {
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[x].p = z;
    if (ntroot(y)) tr[z].s[tr[z].s[1] == y] = x; 
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[y].p = x, tr[x].s[k ^ 1] = y;
    pushup(y); pushup(x);   
}

inline void splay(int x) {
    pushall(x);
    while (ntroot(x)) {
        int y = tr[x].p, z = tr[y].p;
        if (ntroot(y)) {
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}

inline void access(int x) {
    for (int y = 0; x; y = x, x = tr[x].p) 
        splay(x), tr[x].s[1] = y, pushup(x); 
}

inline void makeroot(int x) {
    access(x); splay(x); reverse(x);
}

inline int findroot(int x) {
    access(x); splay(x);
    while (tr[x].s[0]) {
        pushdown(x);
        x = tr[x].s[0];
    }
    splay(x);
    return x;
}

inline void link(int x, int y) {
    makeroot(x);
    if (findroot(y) == x) return;
    tr[x].p = y;
}

inline void cut(int x, int y) {
    makeroot(x);
    if (findroot(y) != x || tr[y].p != x || tr[y].s[0]) return;
    tr[x].s[1] = tr[y].p = 0;
    pushup(x);
}

inline void split(int x, int y) {
    makeroot(x); access(y); splay(y);
}

int main() {
    n = read(), m = read();
    rep(i, 1, n) tr[i].val = read();
    while (m --) {
        int op = read(), x = read(), y = read();
        if (!op) {
            split(x, y);
            printf("%d\n", tr[y].res);
        } else if (op == 1) {
            link(x, y);
        } else if (op == 2) {
            cut(x, y);
        } else {
            splay(x);
            tr[x].val = y;
        }
    } 
    return 0;
}

模板题

P3690 【模板】动态树（LCT）

代码在上面

P1501 [国家集训队] Tree II

考虑运用线段树打懒标记的思路，对于每个 \(Splay\) 结点维护 \(val, mul, add, sum, flag, sz\)，其中 \(val\) 为结点的值，\(mul\) 为乘的懒标记，\(add\) 为加的懒标记，\(sum\) 为子树的和，\(flag\) 是翻转的懒标记，\(sz\) 是子树的大小。

维护懒标记时先 \(mul\) 再 \(add\)，原因可以自己列个式子算一算。

代码

自我感觉马蜂挺良好的？

P4219 [BJOI2014] 大融合

\(A\) 操作就是 \(Link\)，\(Q\) 操作我们可以维护每个子树的 \(sz\)，\(split(x, y)\) 后答案就是 \(sz[x] * (sz[y] - sz[x])\)，这样就做完了，吗？

由于 \(LCT\) 有虚边和实边的分别，所以我们不能单纯地维护实边的 \(sz\)，我们还要加上虚边，所以我们可以再维护一个 \(sz2\) 代表虚边的大小。然后 \(pushup\) 要修改，并且会改变边的虚实关系的 \(access\) 和 \(link\) 中都要维护 \(sz2\)。

注意到 \(link\) 中进行了修改增加了 \(makeroot(y)\)，因为如果直接连 \(y\) 的祖先就爆了。

inline void pushup(int x) {
    tr[x].sz = tr[tr[x].s[0]].sz + tr[tr[x].s[1]].sz + 1 + tr[x].sz2;
}
inline void access(int x) {
    for (int y = 0; x; y = x, x = tr[x].p) 
        splay(x), tr[x].sz2 += tr[tr[x].s[1]].sz - tr[y].sz, tr[x].s[1] = y, pushup(x); 
}
inline void link(int x, int y) {
    makeroot(x); makeroot(y);
    tr[y].sz2 += tr[x].sz, tr[y].sz += tr[x].sz;
    tr[x].p = y;
}

其实解决这个问题的方式还有一种就是 \(link\) 当不需要判断数据合法性时还有另一种写法，直接 \(split(x, y)\) 然后这时 \(x, y\) 相当于一个在链首，一个在链尾，这时候直接搞就不会出问题了。

inline void link(int x, int y) {
    split(x, y);
    tr[x].p = y;
}

完整代码

在更

posted @ 2025-02-02 16:07 はなこくん阅读(82) 评论(0) 收藏举报

刷新页面返回顶部

比翼鼠の博客