LCT 学习笔记

模板及讲解

LCT，也就是Link-Cut Tree的缩写。它是最常见的一种解决动态树问题的工具。不过说它是树也不准确，因为它维护的可以是一片森林。

实链剖分

将某一个儿子的连边划分为实边，而连向其他子树的边划分为虚边。
区别在于虚实是可以动态变化的，因此要使用更高级、更灵活的Splay来维护每一条由若干实边连接而成的实链。
LCT维护的对象其实是一个森林。

LCT 性质

1、每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径，且中序遍历Splay得到的每个点的深度序列严格递增。

2、每个节点包含且仅包含于一个Splay中

3、边分为实边和虚边，实边包含在Splay中，而虚边总是由一棵Splay指向另一个节点（指向该Splay中中序遍历最靠前的点在原树中的父亲）。

LCT 操作

LCT 支持以下几种操作：

核心操作
1、void access(int x)：原树中将 $x$ 和根之间的路径变为实边，并且让 $x$ 成为所在的重链中的深度最大的结点

辅助操作
Splay操作
1、int rel(int x)
2、void pushup(int x)
3、void pushdown(int x)
4、void rotate(int x)
LCT操作
1、int isRt(int x)：$x$是当前Splay的根吗
2、void makeRt(int x)：在原树中换根
3、int findRt(int x)：在原树中找$x$的根

实现操作
1、void link(int x, int y)：在原树中连边 $(x,y)$
2、void cut(int x, int y)：在原树中断边 $(x,y)$
2、void split(int x, int y)：在原树中提取路径 $(x,y)$

核心操作实现

1、access：

原树中将 $x$ 和根之间的路径变为实边，并且让 $x$ 成为所在的重链中的深度最大的结点

其它所有的操作都是在此基础上完成的。
因为性质$3$，我们不能总是保证两个点之间的路径是直接连通的（在一个Splay上）。
$access$即定义为打通根节点到指定节点的实链，使得一条中序遍历以根开始、以指定点结束的Splay出现。

图见Link Cut Tree(动态树) - linjiayang2016的博客 - CSDN博客

void access(int x) { // 在原树中将 x 和根之间的路径变为实边，并且让 x 成为所在的重链中的深度最大的结点 
    for (int y = 0; x; y = x, x = fa[x]) 
        splay(x), rc = y, pushup(x);
}

辅助操作

Splay操作

有些地方与普通 Splay 不同，详情看代码

void rotate(int x) { // 同 Splay
    pushdown(fa[x]), pushdown(x);
    int y = fa[x], z = fa[y], k = rel(x), w = ch[x][k ^ 1];
    if (!isRt(y)) ch[z][rel(y)] = x;
    fa[x] = z; // y 是根则 (z, y) 为轻边，父不认子 (与普通 Splay 不同之处 1) 
    ch[y][k] = w, fa[w] = y;
    ch[x][k ^ 1] = y, fa[y] = x;
    pushup(y), pushup(x);
}
void splay(int x) { // 同 Splay
    top = 0;
    stk[++top] = x;
    for (int pos = x; !isRt(pos); pos = fa[pos]) stk[++top] = fa[pos];
    while (top) pushdown(stk[top--]); // 将 x 到根的路径上的点从上面到下面 pushdown (与普通 Splay 不同之处 2) 
    //疑难点1：因为在普通Splay中(文艺平衡树)kth的时候pushdown了，所以要先pushdown 
    while (!isRt(x)) { // (与普通 Splay 不同之处 3.1) 
        int y = fa[x];
        if (!isRt(y)) { // (与普通 Splay 不同之处 3.2) 
            if (rel(x) == rel(y)) rotate(y); else rotate(x);
        }
        rotate(x);
    }
    //pushup(x); 好像不必要?  
}

LCT操作

isRt:

$x$是当前Splay的根吗

判断一下父亲是否没有指向该点即可。
因为根一定和父亲连轻边，轻边父亲不认孩子，孩子认父亲

int isRt(int x) {return ch[fa[x]][0] != x && ch[fa[x]][1] != x;} //是当前Splay的根吗

makeRt:

在原树中换根

先将$x$和根打通，然后再splay到根
然后发现这个没有右孩子，我们可以考虑翻转左右孩子来解决(打标记)

图见Link Cut Tree(动态树) - linjiayang2016的博客 - CSDN博客

void makeRt(int x) { // 在原树中换根 
    access(x), splay(x);
    prorev(x);
}

findRt(int x):

在原树中找$x$的根

一般用来判连通性findRt(x)==findRt(y)，可以类比并查集
先将$x$和根打通，然后再splay到根
然后现在根和$x$在一个splay，并且根是splay中深度最小的，那么不断找左孩子即可。
注意pushdown

假如LCT题目在维护连通性的情况中只可能出现合并而不会出现分离的话，可以用并查集减小常数

int findRt(int x) { // 在原树中找 x 的根 
    access(x), splay(x);
    while (pushdown(x), lc) x = lc;
    splay(x); // splay 保持平衡 
    return x;
}

实现操作

link:

在原树中连边 $(x,y)$

要判断是否已经连通。
先将$x$转成根，然后再找$y$的根是否和$x$相同(是否连通)，若连通则连边

void link(int x, int y) { // 在原树中连边 x-y 
    makeRt(x);
    if (findRt(y) != x) fa[x] = y;
}

cut:

在原树中断边 $(x,y)$

要判断是否已经不连通。
先将$x$转成根，然后要判三个条件
1、连通性
2、$x,y$是否有父子关系
3、看$y$是否有左儿子

void cut(int x, int y) { // 在原树中断边 x-y 
    makeRt(x);
    if (findRt(y) == x && fa[y] == x && !ch[y][0]) {
        fa[y] = ch[x][1] = 0;
        pushup(x);
    }
}

如果维护了$size$，还可以换一种判断

findRt(y) != x || sz[x] > 2

解释一下，如果他们有直接连边的话，$access(y)$以后，为了满足性质$1$，该Splay只会剩下$x,y$两个点了。
反过来说，如果有其它的点，$size$就大于$2$了

split:

在原树中提取路径 $(x,y)$

void split(int x, int y) { // 在原树中提取路径 x-y 
    makeRt(x);
    access(y), splay(y); // splay 保持平衡 
    //疑难点2：根(x)与y形成一条重链，并且根据 access 性质，y 是最深的节点，该操作成立 
}

模板题：【模板】Link Cut Tree （动态树）
代码：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    #define lc ch[x][0]
    #define rc ch[x][1]

    const int MAXN = 300000 + 5;

    int ch[MAXN][2], fa[MAXN], val[MAXN], xorv[MAXN], rev[MAXN];
    // ch: 节点左右子树，fa: 父亲节点，val: 节点值，xorv: 异或和标记， rev: 翻转标记 
    int n, m, top, stk[MAXN];

    int isRt(int x) {return ch[fa[x]][0] != x && ch[fa[x]][1] != x;} //是当前Splay的根吗 
    int rel(int x) {return ch[fa[x]][1] == x;} // 同 Splay
    void prorev(int x) {swap(lc, rc), rev[x] ^= 1;} // 处理翻转操作 (简化代码) 
    void pushup(int x) {xorv[x] = xorv[lc] ^ xorv[rc] ^ val[x];} //上传标记
    void pushdown(int x) { //下传标记
        if (rev[x]) {
            if (lc) prorev(lc);
            if (rc) prorev(rc);
            rev[x] = 0;
        }
    }
    void rotate(int x) { // 同 Splay
        pushdown(fa[x]), pushdown(x);
        int y = fa[x], z = fa[y], k = rel(x), w = ch[x][k ^ 1];
        if (!isRt(y)) ch[z][rel(y)] = x;
        fa[x] = z; // y 是根则 (z, y) 为轻边，父不认子 (与普通 Splay 不同之处 1) 
        ch[y][k] = w, fa[w] = y;
        ch[x][k ^ 1] = y, fa[y] = x;
        pushup(y), pushup(x);
    }
    void splay(int x) { // 同 Splay
        top = 0;
        stk[++top] = x;
        for (int pos = x; !isRt(pos); pos = fa[pos]) stk[++top] = fa[pos];
        while (top) pushdown(stk[top--]); // 将 x 到根的路径上的点从上面到下面 pushdown (与普通 Splay 不同之处 2) 
        //疑难点1：因为下面 isRt 的调用，所以要先pushdown 
        while (!isRt(x)) { // (与普通 Splay 不同之处 3.1) 
            int y = fa[x];
            if (!isRt(y)) { // (与普通 Splay 不同之处 3.2) 
                if (rel(x) == rel(y)) rotate(y); else rotate(x);
            }
            rotate(x);
        }
        //pushup(x); 好像不必要?  
    }
    void access(int x) { // 在原树中将 x 和根之间的路径变为实边，并且让 x 成为所在的重链中的深度最大的结点 
        for (int y = 0; x; y = x, x = fa[x]) 
            splay(x), rc = y, pushup(x);
    }
    void makeRt(int x) { // 在原树中换根 
        access(x), splay(x);
        prorev(x);
    }
    int findRt(int x) { // 在原树中找 x 的根 
        access(x), splay(x);
        while (pushdown(x), lc) x = lc;
        splay(x); // splay 保持平衡 
        return x;
    }
    void split(int x, int y) { // 在原树中提取路径 x-y 
        makeRt(x);
        access(y), splay(y); // splay 保持平衡 
        //疑难点2：根(x)与y形成一条重链，并且根据 access 性质，y 是最深的节点，该操作成立 
    }
    void link(int x, int y) { // 在原树中连边 x-y 
        makeRt(x);
        if (findRt(y) != x) fa[x] = y;
    }
    void cut(int x, int y) { // 在原树中断边 x-y 
        makeRt(x);
        if (findRt(y) == x && fa[y] == x && !ch[y][0]) {
            fa[y] = rc = 0;
            pushup(x);
        }
    }

    void clean() {
        ms(ch, 0), ms(fa, 0), ms(val, 0), ms(xorv, 0), ms(stk, 0), ms(rev, 0);
    }
    int solve() {

        clean();
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) scanf("%d", &val[i]);
        for (int t, x, y, i = 1; i <= m; ++i) {
            scanf("%d%d%d", &t, &x, &y);
            if (t == 0) 
                split(x, y), printf("%d\n", xorv[y]);
            if (t == 1)
                link(x, y);
            if (t == 2) 
                cut(x, y);
            if (t == 3)
                splay(x), val[x] = y;
        }

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

写时注意
1、split和findRt要Splay保持平衡

应用

1、动态维护最小生成树
Bzoj 3669

参考资料

• LCT总结——概念篇 - Flash_Hu - 博客园：大部分思路
• Link Cut Tree(动态树) - linjiayang2016的博客 - CSDN博客：参考图片资源
• Link-Cut-Tree - 作业部落 Cmd Markdown 编辑阅读器：LCT的Splay与普通Splay区别的写法

若本文侵犯了您的权益，请联系我删除，谢谢