Link-Cut Tree

发表于 分类于 ，

概述:

LCT 是用于维护动态森林的数据结构。可以做到 \(O(\log n)\) 的查询，切割，连接操作.

LCT 基于树链剖分的思想，即将一棵树剖成多条树链， 方便采用数据结构处理.

具体来说，LCT 采用了” 实链剖分”, 即每个点指定一个” 实儿子”, 通过” 实儿子” 连成” 实链”. 与普通的树链剖分区别在于” 实儿子” 是动态变化的.

LCT 使用 splay 来维护树链. 由于一条树链上的节点点深度各不相同. 所以可以使用深度作为关键字建立 splay. 每个节点的左子树深度比该节点小，右子树深度比该节点大.

树链之间的连接关系可以在 splay 的树根上做文章: 将 splay 的根的父节点指向这个 splay 对应树链深度最小的点在原树上的父节点. 这样整棵树便连接起来了，同时区分出了树上的虚实关系：实边双向连接， 虚边单向连接.

操作:

需要实现 LCT 首先需要实现 splay, 以 luoguP3690 为例， 代码与节点定义如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
struct td {
    int v,sm,sz;    //节点值, 异或和, splay子树大小
    bool tr;    //翻转标记
    int fa, sn[2];  //父指针, 左右儿子指针
}t[Mn]; //节点空间

int idn(int x) {    //父子节点关系(x是其父节点的左/右儿子)
    if(t[t[x].fa].sn[0] == x) {
        return 0;
    } else if(t[t[x].fa].sn[1] == x) {
        return 1;
    } else {
        return -1;
    }
}
void psd(int x) {   //懒标记下放
    if(t[x].tr) {
        swap(t[t[x].sn[0]].sn[0],t[t[x].sn[0]].sn[1]);
        swap(t[t[x].sn[1]].sn[0],t[t[x].sn[1]].sn[1]);
        t[t[x].sn[0]].tr ^= 1;
        t[t[x].sn[1]].tr ^= 1;
        t[x].tr = 0;
    }
}
void mtn(int x) {   //维护
    t[x].sz = t[t[x].sn[0]].sz + t[t[x].sn[1]].sz + 1;
    t[x].sm = t[t[x].sn[0]].sm ^ t[t[x].sn[1]].sm ^ t[x].v;
}
void rot(int x) {   //将x向上旋转
    int fx(t[x].fa), gx(t[fx].fa);
    psd(fx), psd(x);
    int d(idn(x)), df(idn(fx));
    t[fx].sn[d] = t[x].sn[d^1];
    t[x].sn[d^1] = fx;
    t[t[fx].sn[d]].fa = fx;
    t[fx].fa = x;
    t[x].fa = gx;
    if(df!=-1) {
        t[gx].sn[df] = x;
    }
    mtn(fx), mtn(x);
}
void psdPath(int x) {   //递归下放标记
    if(idn(x)!=-1) {
        psdPath(t[x].fa);
    }
    psd(x);
}
void spl(int x) {   //伸缩
    psdPath(x);
    while(idn(x)!=-1) {
        if (idn(t[x].fa) != -1) {
            rot((idn(x)==idn(t[x].fa)) ? t[x].fa : x);
        }
        rot(x);
    }
}

access(x)

将根到 x 的所有边变为实边，这条路径上节点的其余边全部变为虚边. 此时 x 为根所在的实链中最深的节点.

本质上就是将 x 接入根所在的 splay 中。由于 LCT 的特性， 需要从下往上处理.

首先使用 splay 的操作将 x 伸缩到其所在 splay 的根. 此时其 splay 右子树为深度比 x 大的实链节点，需要将其断开.

同时由于 x 在实链 splay 的根上， 其父指针指向了这个 splay 对应实链深度最小的点在原树上的父节点. 将该节点的右儿子设为 x, 就使得 x 所在实链与上面的实链连接起来了.

重复这个步骤直到 x 的父指针为空，access 操作就完成了.

1
2
3
4
5
6
7
void acs(int x) {
    for(int y(0); x; y=x, x=t[x].fa) {
        spl(x); //伸展到根
        t[x].sn[1] = y; //实链连接
        mtn(x); //维护
    }
}

makeroot(x)

将 x 变为原树的根.

这个操作的作用主要是进行原树上的路径操作， 将路径的其中一个点变为根后对另一个点 access 即可在一个 splay 中进行原树上的路径操作.

将 x access 后将 x 和根所在的 splay 翻转即可. 可以脑补一下将 x 到原根这条链的深度翻转的结果.

1
2
3
4
5
void mkr(int x) {
    acs(x); spl(x);
    swap(t[x].sn[0],t[x].sn[1]);    //翻转
    t[x].tr ^= 1;   //打上翻转标记
}

findroot(x)

寻找 x 所在的原树的根.

这个操作可以用来判断两个节点是否在同一个树中， 也即将 LCT 视作一个支持删边的” 并查集”.

将 x access 后寻找 x 所在 splay 中深度最小的节点即可.

1
2
3
4
5
6
7
8
int fdr(int x) {
    acs(x); spl(x);
    while(t[x].sn[0]) {
        psd(x); x = t[x].sn[0]; //注意先下传标记再向下遍历
    }
    spl(x); //将根伸展可以使得一些操作更加方便
    return x;
}

link(x,y)

连接 x 和 y.

makeroot y 后 access 并 splay x 然后再将 y 的父节点设为 x (即 x 与 y 连接一条虚边).

将 x access 并 splay 是为了维护节点 x.

注意先判断 x 与 y 是否在同一棵树上.

1
2
3
4
5
6
7
8
9
void lnk(int x,int y) {
    if(rand()&1) {  //随机化
        swap(x,y);
    }
    mkr(y);
    if(fdr(x)!=y) { //findroot x时已经将x access和splay
        t[y].fa = x;
    }
}

cut(x,y)

断开 x 与 y 的边.

makeroot x 后首先使用 findroot y 判断 x 与 y 是否在同一棵树上， 若 x 与 y 有边连接则 y 为 x 的右儿子且 y 没有左儿子。此时断开 x 与 y 的连接即可.

1
2
3
4
5
6
7
void cut(int x,int y) {
    mkr(x);
    if(fdr(y)==x && t[y].fa==x && !t[y].sn[0]) {    //判断是否有边
        t[x].sn[1] = t[y].fa = 0;   //断开
        mtn(x); //splay结构改变需要重新维护
    }
}

一些技巧:

边权变点权:

一些题目需要维护的是边权而不是点权，此时可以将原树上的边也看作点， 点权即为原树上的边权。加边删边时将对应边的点两边连边删边即可.

由于森林的边数最多为 n-1 条，所以空间增加了一倍.

维护子树信息:

维护子树信息需要每个节点同时维护实子树与虚子树的信息， 而 LCT” 认父不认子” 的特性使得虚子树的信息不太方便维护.

解决的方法是对每个点统计其所有虚子树的贡献 , 并且在涉及改变 splay 形态的操作中即时修改.

access 操作中每次循环中当前 splay 的根节点的原右儿子与新右儿子的虚实发生了变化， 此时需要减去新右儿子的贡献并加上原右儿子的贡献.

link 操作连接了一条虚边，所以此时需要加上新虚儿子的贡献.

可以看出使用 LCT 维护的子树信息需要满足可减性 , 例如子树权值和，反例是子树最大值. 否则在 access 操作中无法维护虚子树信息.