Link-Cut-Tree(LCT)详解
Link-Cut-Tree(LCT)详解
前置知识
基础定义
LCT是一种解决动态树问题的方法，由tarjan(为什么又是他)在1982年提出，最原始的论文在这里,在论文中，tarjan除了介绍了均摊复杂度为\(O(log^2n)\)的LCT之外，还介绍了一种严格\(O(log^2n)\)的算法，不过本人太弱了，看不懂tarjan讲了些啥，也没找到其他的学习资料，因此这种算法我们不做讨论
能够解决的问题
- 求LCA
- 求最小生成树
- 维护链上信息(最大最小，链上和等)
- 维护联通性
- 维护子树信息(需要配合AAA树)
- 优化单纯性算法，在\(O(mnlog(n))\)的复杂度下求最大流（这两个是tarjan在它的论文最开头提到的，但是我除了在一本书中看到过有关的简介(没有代码)之外，再没看到过关于它的任何资料，）
构造
在解决树上问题的时候，有一种非常常见的操作叫做链剖分
链剖分一般分为三种
- 重链剖分，也就是我们常提到的“树剖”，剖分的原理是把节点个数最多的儿子当做重儿子
- 长链剖分，并不是很常见，可以\(O(1)\)求\(k\)级祖先，原理是把深度最深的儿子当做重(长)儿子
- 实链剖分，也就是LCT所用到的剖分方法，这里重点介绍一下
在实链剖分时，选择一个儿子作为重儿子，把连接这两个节点的边作为重边，连接其他儿子的边作为轻边。
与前两种剖分不同的是，实链剖分中的重儿子是可以不断变化的，因此在整棵树中的重链和轻链也是在不断变化的，这就需要我们用更灵活一些的数据结构来维护。
维护一条链，我们首先可以想到的是链表，但是用链表来维护树上权值和的话时间复杂度肯定是\(O(n^2)\)的，即使是块状链表也只能做到\(O(n \sqrt{n})\)
因此我们用平衡树来维护链上信息，那么用什么平衡树呢？理论上splay和fhq treap都是可以的，treap不可以，因为不能维护翻转信息，在这里我比较推荐splay，因为网上有关LCT的题目大多数题解都是用splay写的，这样的话学习难度也会小一点，而且我自测splay的常数要比fhq treap小很多
我们用splay维护每一条实路径(仅由实边组成的路径)，因为每条实路径都对应一条从根节点出发的链，这样的话路径上每个节点的深度都是不同的，因此在splay中，我们按深度作为关键字，对于一个节点，它的左孩子所对应的原节点深度比它小，右儿子所对应的原节点深度比它大
（这里插一句闲话，LCT之所以难于理解，很大程度上是初学者分不清原树/splay，因此我希望大家在继续往下读的过程中，一定要分清楚我所说的概念到时指的是原树还是splay树）
但是这样的话，虽然每个节点都包含在了splay中，但是每个splay之间都是独立的，因此我们要考虑如何在各个splay中建立联系， 对于一个节点，假设它有三个儿子，其中最多有一个节点可以和他在一个splay中，另外两个儿子分别属于不同的splay。这里有一个非常巧妙的性质——另外两个儿子在他们所在的子树中一定是深度最小的，因此我们可以让每个splay中的根节点指向splay中 中序遍历编号最小(也就是原树中深度最小)的节点的父亲，有点绕，希望大家好好理解一下
对于一棵这样的树 (图片来源：FlashHu的博客)
它的splay树可能长这个样子
LCT基础操作
\(access(x)\)
将根节点到\(x\)点的路径变为实路径，且\(x\)与其儿子之间的边都变为虚边。
首先考虑一下这个操作有什么目的，有了这个操作，我们就可以将根节点到\(x\)的这条路径放在同一棵splay中，这样可以很方便通过在splay上打标记得到路径信息
具体怎么实现呢？
还是上面那张图
如果我们要执行\(access(N)\)，
我们可以从下往上依次处理，首先我们要使得\(N-O\)这条边变为轻边，因为在splay中，节点的深度是唯一的，所以我们首先把\(N\)，转到根节点，这样它右边的节点一定是\(O\)，然后直接把\(N\)节点的右儿子置为\(0\)就可以了
继续往上，我们需要使\(I-K\)这条边变为轻边，同时使\(I-L\)这条边变为重边
考虑如何使\(I-K\)变为轻边。和上面的思路一样，我们首先使\(I\)转到所在splay的根节点，这样的话它的右儿子一定是\(K\)，然后我们只需要断开\(I-K\)这条边即可
考虑如何使\(I-L\)变为重边。这个就so easy了，直接将\(I\)的右儿子置为\(L\)即可
此时\(I\)所在的splay的父亲指向\(H\)
继续往上思路就是一样的了，按照同样的套路使得\(H-J\)变为轻边，使\(H-I\)变为重边，
此时\(H\)指向\(A\)，然后让\(A\)转到所在splay的根节点，把右儿子置为\(H\)即可
这样我们就实现了\(access\)操作，按照上面的流程，我们不难总结出算法框架
- 将要处理的节点转到根
- 更改右儿子
- 更新标记
代码的话，，首先说一下各种定义
struct node {
int f, ch[2], s;
//f：父亲
//ch[0]/[1]:左/右儿子
//s:标记，依题目而变
bool r;//是否翻转
}T[MAXN];access
void access(int x) {//访问x节点
for(int y = 0; x; x = fa(y = x))
splay(x), rs(x) = y, update(x);
//首先把x splay到所在平衡树的根，这样可以保证它的右孩子就是在原树中对应的重链(右孩子深度比它大)
//y是splay中x的儿子，把x的右儿子改成y，也就是把x和y之间的边变成实边
//更改了节点顺序，需要update
}\(makeroot(x)\)
将\(x\)变为原树的根
考虑这个操作的意义。对于大多数树上询问来说，都是询问一条过根节点的路径，由于LCT的构造的缘故，这种询问处理起来非常麻烦。但是当询问的一端在根节点的时候，处理起来就容易的多，所以这个操作的意义在于帮助我们更好的处理询问
这里有一个非常巧妙的实现思路：
首先我们需要\(access(x)\)，这样我们就把根节点和\(x\)放到了同一棵splay中
此时\(x\)是不含右儿子的（没有深度比他大的点）
然后我们需要\(splay(x)\)，此时\(x\)会成为splay的根节点，且\(x\)不含右儿子。
但是在根节点所在的splay中，根节点没有左儿子（没有深度比他小的节点）
这可怎么办呢？？
这里就有一个骚操作了，我们直接将\(x\)的左右子树翻转！
这样\(x\)不就没有左儿子了么？233
事实证明这样是对的
代码：
void makeroot(int x) {//把x改为原树的根节点
access(x);
splay(x);
T[x].r ^= 1;//更新翻转标记
}\(findroot(x)\)
找到\(x\)所在原树的根
你刚开始可能跟我一样很呆萌的认为：\(x\)所在原树的根不就是根节点么？
但是。。
有一点需要注意：LCT维护的是森林，也就是很多棵树，因此每个节点所在原树的根节点往往是不同的
考虑这个操作的意义：
大家有没有发现，这个操作跟并查集中找祖先的操作很类似？没错，这个操作的用处就是判断两个节点的联通性（是否在同一棵树上）
实现的话，我们利用了一个性质：一棵树的根节点一定是深度最小的点
这样我们先\(accexx(x)\)，然后\(splay(x)\)，再不断的往左走，这样就可以找到\(x\)所在树的根节点了！
注意！往左走的时候一定要下传标记，否则在某些题目中你会挂的很惨！
代码
int findroot(int x) {//找到x在原树中的根节点
access(x);splay(x);
pushdown(x);
while(ls(x)) pushdown(x = ls(x));//找到深度最小的点即为根节点
return x;
}\(split(x,y)\)
获取到\(x-y\)所对应的路径，
这个操作的意义就非常显然了
实现也非常好想，直接上代码吧
这样的话可以通过访问\(y\)节点来获取到有关路径的信息
void split(int x, int y) {
makeroot(x);//首先把x置为根节点
access(y); splay(y);
//然后访问一下y，再把y转到根节点，这样y维护的就是x - y 路径上的信息
}\(link(x,y)\)
连接\(x,y\)
这个操作的意义也很显然
首先我们需要\(makeroot(x)\)，然后\(access(y),splay(y)\)，最后把\(x\)的父亲指向\(y\)就可以
注意在一些毒瘤题中不保证\(x,y\)未联通，这样还需要判断一下联通性
void link(int x, int y) {
makeroot(x);//把x置为根节点
if(findroot(y) != x ) fa(x) = y;
//如果x与y不在同一个splay中，就把y置为x的父亲
//findroot(y)的时候已经执行了access(y),splay(y)
}\(cut(x,y)\)
断开\(x-y\)这条边
意义也非常显然
实现的话看上去比较容易
我们需要\(split(x,y)\)，此时\(x\)的父亲是\(y\)，\(y\)因为是深度最深的点，所以它的左儿子是\(x\)，
然后断绝父子关系就好了
但是！！，如果出题人不保证\(x-y\)相连呢？？
如果仍然这样改的话整棵树就乱了
因此我们还要加一坨判断
- 首先\(x,y\)一定要在一棵树内
- \(x\)的父亲是\(y\)，且\(y\)的左儿子是\(x\) 这两个比较显然
- \(x\)没有右儿子
这个可能就不是那么显然了
我们仔细考虑一下，\(x\)的右儿子代表着深度比他大的节点，\(y\)的左儿子代表着深度比他小的节点
那如果出现这种情况呢？
然后我们就GG了，
或者你可以试试这组数据
5 6 1 2 3 4 5
1 1 2
1 2 3
1 3 4
1 4 5
2 1 5
0 1 5因此我们有必要加上这个判断
代码：
void cut(int x, int y) {
makeroot(x);
if(findroot(y) == x && fa(x) == y && ls(y) == x && !rs(x)) {
fa(x) = T[y].ch[0] = 0;
update(y);
}
}时间复杂度
以上操作的平摊复杂度均为\(O(log^2N)\)
具体的证明可以参考YangZhe的论文
小结
LCT的操作也就是这么多了，
不过LCT有很多拓展，题目类型也有很多，大部分我还没做过
等以后慢慢整理吧
洛谷的板子题代码：
其中的splay和rotate都是我自己yy的，并不是很主流的写法，不过跑的比较快
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define swap(x,y) x ^= y, y ^= x, x ^= y
const int MAXN=3 * 1e5 + 10;
inline int read()
{
char c = getchar();int x = 0,f = 1;
while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();}
return x * f;
}
#define fa(x) T[x].f
#define ls(x) T[x].ch[0]
#define rs(x) T[x].ch[1]
int v[MAXN];
struct node {
int f, ch[2], s;
bool r;
}T[MAXN];
int ident(int x) {
return T[fa(x)].ch[0] == x ? 0 : 1;//判断该节点是父亲的哪个儿子
}
int connect(int x,int fa,int how) {
T[x].f=fa;
T[fa].ch[how]=x;//连接
}
inline bool IsRoot(int x) {//若为splay中的根则返回1 否则返回0
return ls( fa(x) ) != x && rs( fa(x) ) != x;
//用到了两个性质
//1.若x与fa(x)之间的边是虚边，那么它的父亲的孩子中不会有他（不在同一个splay内）
//2. splay的根节点与其父亲之间的边是虚边
}
void update(int x) {
T[x].s = T[ls(x)].s ^ T[rs(x)].s ^ v[x];//维护路径上的异或和
}
void pushdown(int x) {
if(T[x].r) {
swap(ls(x),rs(x));
T[ls(x)].r ^= 1;
T[rs(x)].r ^= 1;
T[x].r = 0;//标记下传
}
}
void rotate(int x) {
int Y = T[x].f, R = T[Y].f, Yson = ident(x), Rson = ident(Y);
int B = T[x].ch[Yson ^ 1];
T[x].f = R;
if(!IsRoot(Y))
connect(x, R, Rson);
//这里如果不判断y是否根节点，那么当y是根节点的时候，0节点的儿子就会被更新为x
//这样x就永远不能被判断为根节点，也就会无限循环下去了
//但是这里不更新x的父亲的话就会出现无限递归的情况
connect(B, Y, Yson);
connect(Y, x, Yson ^ 1);
update(Y); update(x);
}
int st[MAXN];
void splay(int x) {
int y = x, top = 0;
st[++top] = y;
while(!IsRoot(y)) st[++top] = y = fa(y);
//用一个栈维护所有的标记
while(top) pushdown(st[top--]);
//因为在旋转的时候不会处理标记，所以splay之前应该下传所有标记
for(int y = fa(x); !IsRoot(x); rotate(x), y = fa(x))//只要不是根就转
if(!IsRoot(y))
rotate( ident(x) == ident(y) ? x : y );
}
void access(int x) {//访问x节点
for(int y = 0; x; x = fa(y = x))
splay(x), rs(x) = y, update(x);
}
void makeroot(int x) {//把x改为原树的根节点
access(x);
splay(x);
T[x].r ^= 1;
pushdown(x);
}
int findroot(int x) {//找到x在原树中的根节点
access(x);splay(x);
pushdown(x);
while(ls(x)) pushdown(x = ls(x));//找到深度最小的点即为根节点
return x;
}
void split(int x, int y) {
makeroot(x);//首先把x置为根节点
access(y); splay(y);
}
void link(int x, int y) {
makeroot(x);//把x置为根节点
if(findroot(y) != x ) fa(x) = y;
}
void cut(int x, int y) {
makeroot(x);
if(findroot(y) == x && fa(x) == y && ls(y) == x && !rs(x)) {
fa(x) = T[y].ch[0] = 0;
update(y);
}
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
#else
#endif
int N = read(), M = read();
for(int i = 1; i <= N; i++) v[i] = read();
for(int i = 1; i <= M; i++) {
int opt = read(), x = read(), y = read();
if(opt == 0) split(x, y), printf("%d\n",T[y].s);
else if(opt == 1) link(x, y);
else if(opt == 2) cut(x, y);
else if(opt == 3) splay(x), v[x] = y;
}
return 0;
}参考资料
《高级数据结构》-林厚从