LCT学习笔记

为啥要学LCT啊

在开坑之间,我们来先看一段对话:

Q:给你一颗森林,现在不断的连接森林中的两棵树,保证不连出环,多次问你某两个点的连通性?
A(dalao&蒟蒻):这不是SB题吗?显然并查集水过啊。
Q:说的好,但是如果我要删除某些边呢?
A(dalao):那就可持久化并查集啊,你的问题怎么那么水。
A(蒟蒻):........(发出gg的声音)

这时候,如果我们并不想写可持久化并查集的话,就得请出我们大名鼎鼎的林特卡特树了。


啥是林特卡特树啊

LCT实质上就是用splay+树剖思想维护的动态森林。

用人话来说,就是维护一个可以随便删边和连边的森林(注:不能连出环来)

LCT的基础功能有:
  1.连接森林中的两棵树或删除某条边
  2.维护这颗森林的连通性
  3.内定森林中某颗树的根

事实上,LCT还可以做一些包括但不限于维护一些奇奇怪怪的值的鬼畜操作。


咋林特卡特树啊

首先呢,我们的得先了解LCT树[注1]与原森林的关系。

我们的LCT树是由一堆连通块组成的,一个连通块就是原森林中的一颗树。
而每个连通块又由一堆splay组成,每个splay可以理解为每颗原树中树链剖分上的重边。splay与splay之间又有连接关系,即一颗splay的根单向连到另外一颗splay的孩子上,这一堆有单向关系的splay就构成了一个联通块。(可以对应的理解为一个树的树链剖分是有一堆重链组成的,重链在这里以splay的形式出现)。

注1:(虽然这样叫是绝对不正确的,因为T就是tree的缩写,但是为了与LCT算法分开来,我们姑且把LCT维护的东西叫做LCT树)

Acess:

由上定义可以看出,我们要对某个点操作,首先要把这个点的连通块给提到LCT树的根上来(可以类比为splay到根上来),然后还要把这个splay连到到LCT树的根所在的重链上去。
听起来很复杂对不对?的确挺复杂。但是这个操作是LCT最基本的操作,其他所有操作都围绕着它展开。

具体原理可以参考这篇博客的介绍,这里只讲做法:

我们把当前操作的点先splay至它所在的splay的根,把这个根的右孩子连至上一次这样操作的根(即连一条重链),对当前点的父亲重复这个过程。

大概是长成这样:

inline void Access(int x)
    {
        for(int t=0;x!=0;t=x,x=fa[x])
            Splay(x),son[x][1]=t,fa[t]=x,Update(x);//注意这里的update,因为孩子关系变了,要更新根节点的数据

GetRoot:

我们要判断原森林中两个点的连通性,你第一反应是什么?没错,我们只需要判断它们的根是否相同就可以了。因此,我们这里就需要一个getroot函数来得到每个点的根。

方法很简单:我们只需要先Acess这个点使得它所在的splay连通块作为LCT森林的根,把这个点splay到根,再一路向左找就好(因为原树中的根的深度一定是最小的)

代码大概长这样:

inline int FindRoot(int x)
    {
        Access(x),Splay(x);
        while(son[x][0]!=0)
            PushDown(x),x=son[x][0];
        Splay(x);//这里splay是为了让这个点所在的splay更平衡一点
        return x;
    }

MakeRoot:

我们既然维护的是一颗动态的森林,那难免会有连边和删边。为了操作的方便,有时我们需要内定一个点作为原森林中的它所在的树的根。

具体做法是这样的:我们先把它Acess(x),splay(x),让它先处于LCT森林的根,然后在把它的左右子树彻底翻转(即每个孩子都翻转),这里可以通过打标记来降低复杂度。(原理请看上面的链接的博客)

代码这样:

inline void MakeRoot(int x)
    {
        Access(x),Splay(x);
        Mirror(x);
    }

Link:

LCT既然维护了一个森林,连连边都做不了,岂不是很丢人?

link的意思是连接原森林中的一条边。

我们只需要这样做:先getroot来判断一下他们是否已经在同一颗树上了,然后makeroot(x)来内定x作为它所在的树的根,再指定一下它的父亲为y即可(即连一条轻边)

inline int Link(int x,int y)//x->y
    {
        if(FindRoot(x)==FindRoot(y))    return 1;
        MakeRoot(x);
        fa[x]=y;
        return 0;
    }

Split:

我们有时候要在LCT中拉出原森林中的一条边来获取信息或搞点事情,因此,我们需要一个函数来处理这破事。

我们只需要先内定x为根,然后再Acess(y),splay(y),此时,如果这条边存在的话,那么x一定是y的左孩子(因为它们深度相邻且x比y浅)

代码长这样:

inline void Split(int x,int y)//y为根
    {
        MakeRoot(x);
        Access(y),Splay(y);
    }

Cut

LCT的意义就在于此(如果不能Cut,那连并查集都不如,人家一个log,LCT两个log呢),我们需要删除原森林中的一条边的时候,就需要cut操作了。

具体方法如下:先把这条边拉出来(Split),然后再检查一下边是否存在,存在的话双向断边即可。

代码长这样:

inline int Cut(int x,int y)
    {
        Split(x,y);
        if(fa[x]==y and son[y][0]==x)
        {
            fa[x]=son[y][0]=0;
            Update(y);
            return 0;
        }
        return 1;
    }

以上就是LCT的基本操作啦,如果有别的需求,我们可以在splay上多记录一点东西(正如之前专门考splay的题一样)就可以搞定啦。

恭喜你学会了LCT,撒花✿✿ヽ(°▽°)ノ✿


有啥题目练啊

1.P2147 [SDOI2008]洞穴勘测 (LCT维护森林连通性)
2.P3203 [HNOI2010]弹飞绵羊 (LCT维护森林中的每棵树的长度)
3.P2168 [NOI2015]荷马史诗 (LCT维护边权和)

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注