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;
}

连接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操作中无法维护虚子树信息.