LCT

前言

LCT（Link Cut Tree） 支持在森林中动态加边、删边、维护链上信息的数据结构。基于 Splay 和实虚链剖分。请确保你对链剖分以及 Splay 有所了解。

实虚链剖分

同轻重链剖分，每个节点都有实虚两种属性。每个节点最多有 $1$ 个实儿子，从父亲到实儿子的边称为实边，从父亲到虚儿子的边称为虚边，一条由实边构成的极长的链称为实链。与轻重链剖分不同的是节点的实虚是动态指定的，并且一个点所有的儿子可以都是虚儿子。

LCT 维护的是一个 Splay 森林。每一棵 Splay 中维护的是一条实链，Splay 中序遍历得到的序列满足在原树中深度严格从小到大。而虚边则是由虚儿子所在的 Splay 的根指向父亲节点。注意对于每条虚边并不会被父亲记录下来（认父不认子）。在考虑虚边的情况下若干个 Splay 连成一个树，称为辅助树。每个辅助树唯一对应一棵树，但一棵树有很多种可能的辅助树。我们仅需维护辅助树上的信息就可以维护原树信息。

一个例子（实边为实线，虚边为虚线，左侧为原树，右侧为辅助树）：

图 1

LCT

一些变量及辅助函数定义

1
2
3
4
5
6
7
struct node{int fa,ch[2],rev;}t[N];
inline int&son(int x,int k){return t[x].ch[k];}
inline int&ls(int x){return son(x,0);}
inline int&rs(int x){return son(x,1);}
inline int&fa(int x){return t[x].fa;}
inline bool isrs(int x){return rs(fa(x))==x;}
inline bool nroot(int x){return ls(fa(x))==x||rs(fa(x))==x;}

fa 记录在辅助树中的父亲节点（注意：辅助树中的父亲节点不一定是原树中的父亲）。ch[0]是 Splay 中的左儿子，ch[1] 是 Splay 的右儿子。isrs 判断该节点是否是其父亲的右儿子。nroot 判断该节点是否不是其所在 Splay 的根，根据如果是虚边，则不是其父亲的左右儿子即可判断。

信息维护相关函数

1
2
3
inline void push_up(int x){/*根据左右儿子更新维护的信息*/}
inline void push_r(int x){t[x].rev^=1;swap(ls(x),rs(x));}
inline void push_down(int x){if(t[x].rev)push_r(ls(x)),push_r(rs(x)),t[x].rev=0;}

LCT 需要用到区间翻转。push_r 表示将以 $x$ 为根的子树翻转，rev 是翻转标记。push_down 下放标记，根据题目要求有可能还需要在此下放别的标记。push_up 更新信息，需要根据题目自行维护。

rotate

1
2
3
4
5
6
7
8
9
inline void rotate(int x)
{
    int y=fa(x),z=fa(y),p=isrs(x);
    if(nroot(y))son(z,isrs(y))=x;
    son(y,p)=son(x,p^1);
    if(son(x,p^1))fa(son(x,p^1))=y;
    son(x,p^1)=y;fa(y)=x,fa(x)=z;
    push_up(y),push_up(x);
}

将节点 $x$ 和其父亲进行旋转。与普通 Splay 不同的是需要判断 $x$ 节点的父亲是否是这棵 Splay 的根，避免将虚儿子的错误地放到实儿子的位置。

splay

1
2
3
4
5
6
7
8
9
10
11
12
int stk[N];
inline void splay(int x)
{
    int y=x,z=0;stk[++z]=y;
    while(nroot(y))stk[++z]=y=fa(y);
    while(z)push_down(stk[z--]);
    while(nroot(x))
    {
        if(nroot(y=fa(x))) rotate(isrs(y)==isrs(x)?y:x);
        rotate(x);
    }
}

将 $x$ 旋转至 Splay 的根。由于有翻转操作，所以必须把从节点 $x$ 到这个 Splay 的根的路径上所有标记下放才能得到位置正确的左右儿子。需要从上到下下放，用一个栈辅助。请使用双旋 Splay 而不是单旋 Spaly 以保证复杂度。

access

1
inline void access(int x){for(int y=0;x;y=x,x=fa(x))splay(x),rs(x)=y,push_up(x);}

LCT 核心操作。将 $x$ 至当前根的路径变为一条实链，且该实链上没有除这条路径外的其他节点。从 $x$ 开始跳虚边。设当前已经处理到 $y$，先把 $y$ 转至 Splay 的根，将其在辅助树上父亲也转至根，此时父亲的右儿子是原来的实儿子，只需将右儿子替换为 $y$ 就将一条虚边变为实边，然后从 $y$ 的父亲继续向上处理。注意：在最开始的时候 $x$ 的所有儿子都要变为虚儿子，即将 $x$ 的右子树变为 $0$，否则会有 $x$ 的实儿子在最终的实链中。

以 access(6) 为例

图 2

make_root

1
inline void make_root(int x){access(x);splay(x);push_r(x);}

将 $x$ 指定为原树的根。在换根时，只有 $x$ 到当前的根节点的路径上所有点的深度顺序被翻转。所以只需要把这条路径变为一条实链，再将这条实链翻转。

find_root

1
inline int find_root(int x){access(x);splay(x);while(ls(x))push_down(x),x=ls(x);splay(x);return x;}

找 $x$ 在原树中的根节点。首先将 $x$ 到根的路径变为一条实链。再将 $x$ 旋转到根方便操作。根节点在这条路径中必为深度最小的点。只需一直找左儿子即可。注意需要 push_down，否则得到的左右儿子顺序可能相反。为了保证时间复杂度，请将找到的点旋转至根。 find_root 效率较低，如果题目可以用并查集维护联通性，请使用并查集代替 find_root。注意：如果某些题目需要在 LCT 的 Splay 中像 find_root 一样找某些节点，请将找到的节点旋转至根以保证时间复杂度。

split

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

将 $x$ 到 $y$ 的路径变为一条实链，方便进行操作。只需将 $x$ 指定为原树的根，再将 $y$ 到根的路径变为实链。为了方便操作，一般会将 $y$ 旋转到 Splay 的根。

1
inline void link(int x,int y){make_root(x);fa(x)=y;}

在 $x$ 和 $y$ 中连接一条边。新连接的边为虚边。将 $x$ 指定为原树中 $x$ 所在连通块的根。只需将 $x$ 的父亲指定为 $y$ 即可连一条虚边。在 link 时请确保 $x$ 和 $y$ 不连通。否则会导致奇怪问题。

cut

1
inline void cut(int x,int y){split(x,y);fa(x)=ls(y)=0;push_up(y);}

断开 $x$ 到 $y$ 的边。将 $x$ 到 $y$ 的路径变为一个实链，由于 $x$ 到 $y$ 有直接连边，所以 Splay 中仅有 $x$ 和 $y$ 两个节点。由于split默认将 $x$ 指定为根，所以 $x$ 比 $y$ 深度小，必然是 $y$ 的左儿子，相互断开连接即可。$y$ 少了一个儿子需要重新更新信息。在 cut 时请确保 $x$ 和 $y$ 有直接连边，否则会导致奇怪问题。在替换树上的边时需要先 cut 再 link，否则连边不合法。

参考资料

总结
#平衡树 #树链剖分
LCT
https://www.llingy.top/posts/1145686937/
作者
llingy
发布于
2022年12月4日
许可协议