欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Link-Cut-Tree(LCT)详解

程序员文章站 2022-04-15 17:35:07
前置知识 必须要理解 "splay" 最好学过 "树链剖分" 基础定义 LCT是一种解决动态树问题的方法,由tarjan~~(为什么又是他)~~在1982年提出,最原始的论文在 "这里" ,在论文中,tarjan除了介绍了均摊复杂度为$O(log^2n)$的LCT之外,还介绍了一种严格$O(log^ ......

前置知识

基础定义

LCT是一种解决动态树问题的方法,由tarjan(为什么又是他)在1982年提出,最原始的论文在这里,在论文中,tarjan除了介绍了均摊复杂度为\(O(log^2n)\)的LCT之外,还介绍了一种严格\(O(log^2n)\)的算法,不过本人太弱了,看不懂tarjan讲了些啥,也没找到其他的学习资料,因此这种算法我们不做讨论

能够解决的问题

  1. 求LCA
  2. 求最小生成树
  3. 维护链上信息(最大最小,链上和等)
  4. 维护联通性
  5. 维护子树信息(需要配合AAA树)
  6. 优化单纯性算法,在\(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的博客)

Link-Cut-Tree(LCT)详解

它的splay树可能长这个样子

Link-Cut-Tree(LCT)详解

LCT基础操作

\(access(x)\)

将根节点到\(x\)点的路径变为实路径,且\(x\)与其儿子之间的边都变为虚边。

首先考虑一下这个操作有什么目的,有了这个操作,我们就可以将根节点到\(x\)的这条路径放在同一棵splay中,这样可以很方便通过在splay上打标记得到路径信息

具体怎么实现呢?

还是上面那张图

Link-Cut-Tree(LCT)详解

如果我们要执行\(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\)操作,按照上面的流程,我们不难总结出算法框架

  1. 将要处理的节点转到根
  2. 更改右儿子
  3. 更新标记

代码的话,,首先说一下各种定义

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\)相连呢??

如果仍然这样改的话整棵树就乱了

因此我们还要加一坨判断

  1. 首先\(x,y\)一定要在一棵树内
  2. \(x\)的父亲是\(y\),且\(y\)的左儿子是\(x\)
    这两个比较显然

  3. \(x\)没有右儿子

这个可能就不是那么显然了

我们仔细考虑一下,\(x\)的右儿子代表着深度比他大的节点,\(y\)的左儿子代表着深度比他小的节点

那如果出现这种情况呢?

Link-Cut-Tree(LCT)详解

然后我们就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;
}

参考资料

FlashHu的博客

YangZhe-QTREE解法的一些研究

《高级数据结构》-林厚从