LCT(Link-Cut Tree)详解(蒟蒻自留地)

2023-10-31 08:32
文章标签 详解 link tree cut lct 自留地

本文主要是介绍LCT(Link-Cut Tree)详解(蒟蒻自留地),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 最近自学了LCT,发现网上的资料讲解不是很全面,像我这样的蒟蒻一时半会根本理解不了。我弄了很久总算是理解了LCT,打算总结一下LCT的基本操作,还请诸位神牛来找找茬。

 

如果你还没有接触过LCT,你可以先看一看这里:

(看不懂没关系,先留个大概的印像)http://www.cnblogs.com/BLADEVIL/p/3510997.html

看完之后我们知道,LCT和静态的树链剖分很像。怎么说呢?这两种树形结构都是由若干条长度不等的“重链”和“轻边”构成(名字可以不同,大概就是这个意思),“重链”之间由”轻边”连接。就像这样:


可以想象为一棵树被人为的砍成了一段段。


        LCT和树链剖分不同的是,树链剖分的链是不会变化的,所以可以很方便的用线段树维护。但是,既然是动态树,那么树的结构形态将会发生改变,所以我们要用更加灵活的维护区间的结构来对链进行维护,不难想到Splay可以胜任。如何分离树链也是保证时间效率的关键(链的数量和长度要平衡),树链剖分的“重儿子”就体现了前人博大精深的智慧。


        在这里解释一下为什么要把树砍成一条条的链:我们可以在logn的时间内维护长度为n的区间(链),所以这样可以极大的提高树上操作的时间效率。在树链剖分中,我们把一条条链放到线段树上维护。但是LCT中,由于树的形态变化,所以用能够支持合并、分离、翻转等操作的Splay维护LCT的重链(注意,单独一个节点也算是一条重链)。

        这时我们注意到,LCT中的轻边信息变得无法维护。为什么呢?因为Splay只维护了重链,没有维护重链之间的轻边;而LCT中甚至连根都可以不停的变化,所以也没法用点权表示它父边的边权(父亲在变化)。所以,如果在LCT中要维护边上信息,个人认为最方便的方法应该是把边变成一个新点和两条边。这样可以把边权的信息变成点权维护,同时为了不影响,把真正的树上节点的点权变成0,就可以用维护点的方式维护边。

 

LCT的各种操作:

        LCT中用Splay维护链,这些Splay叫做“辅助树“。辅助树以它上面每个节点的深度为关键字维护,就是辅助树中每个节点左儿子的深度小于当前节点的深度,当前节点的深度小于右儿子的深度。

        可以把LCT认为是一个由Splay组成的森林,就像这样:(三角形代表一棵Splay,对应着LCT上一条链)


 

箭头是什么意思呢?箭头记录着某棵Splay对应的链向上由轻边连着哪个节点,可以想象为箭头指向“Splay 的父亲”。但是,Splay的父亲并不记录有这个儿子,即箭头是单向的。同时,每个节点要记录它是否是它所在的Splay的根。这样,Splay构成的森林就建成了。


这个是我的Splay节点最基本的定义:(如果要维护更多信息就像Splay维护区间那样加上更多标记)

struct node{int fa,ch[2]; //父亲和左右儿子。bool reverse,is_root;   //区间反转标记、是否是所在Splay的根
}T[maxn];


LCT中基本的Splay上操作:

int getson(int x){return x==T[T[x].fa].ch[1];
}
void pushreverse(int x){if(!x)return;swap(T[x].ch[0],T[x].ch[1]);T[x].reverse^=1;
}
void pushdown(int x){if(T[x].reverse){pushreverse(T[x].ch[0]);pushreverse(T[x].ch[1]);T[x].reverse=false;}
}
void rotate(int x){if(T[x].is_root)return;int k=getson(x),fa=T[x].fa;int fafa=T[fa].fa;pushdown(fa);pushdown(x);    //先要下传标记T[fa].ch[k]=T[x].ch[k^1];if(T[x].ch[k^1])T[T[x].ch[k^1]].fa=fa;T[x].ch[k^1]=fa;T[fa].fa=x;T[x].fa=fafa;if(!T[fa].is_root)T[fafa].ch[fa==T[fafa].ch[1]]=x;else T[x].is_root=true,T[fa].is_root=false;//update(fa);update(x);    //如果维护了信息,就要更新节点
}
void push(int x){if(!T[x].is_root)push(T[x].fa);pushdown(x);
}
void Splay(int x){push(x);   //在Splay到根之前,必须先传完反转标记for(int fa;!T[x].is_root;rotate(x)){if(!T[fa=T[x].fa].is_root){rotate((getson(x)==getson(fa))?fa:x);}}
}






access操作:

这是LCT最核心的操作。其他所有操作都要用到它。

他的含义是”访问某节点“。作用是:对于访问的节点x,打通一条从树根(真实的LCT树)到x的重链;如果x往下是重链,那么把x往下的重边改成轻边。可以理解为专门开辟一条x到根的路径,由一棵Splay维护这条路径。

access之前:(粗的是重链)        access之后:

 

access实现的方式很简单;

        先把x旋转到所在Splay的根,然后把x的右孩子的is_root设为true(此时右孩子对应的是x下方的重链,这样就断开了x和下方的重链)。

        用y记录上一次的x(初始化y=0),把y接到x的右孩子上,这样就把上一次的重链接到了当前重链一起,同时记得T[y].is_root=false。

        记录y=x,然后x=T[x].fa,把x上提。重复上面的步骤直到x=0。

代码:

void access(int x){int y=0;do{Splay(x);T[T[x].ch[1]].is_root=true;T[T[x].ch[1]=y].is_root=false;//update(x);    //如果维护了信息记得更新。x=T[y=x].fa;}while(x);
}




mroot操作:

         这个操作的作用是把某个节点变成树根(这里的根指的是整棵LCT的根)。加上access操作,就可以方便的提取出LCT上两点之间的路径。提取u到v的路径只需要mroot(u),access(v),然后v所在的Splay对应的链就是u到v的路径。

mroot实现的方式:

         由于LCT是Splay组成的森林,所以要把x变成根就只需要让所有Splay的父亲最终指向x所在Splay。所以先access(x),Splay(x),把现在的根和将成为根的x链在一棵Splay中,并转到根即可。但是我们注意到,由于x成为了新的根,所以它和原来的根所在的Splay中深度作为关键字的性质遭到了破坏:新根x应该是Splay中深度最小的,但是之前的操作并不会改变x的深度(也就是目前x依旧是当前Splay中深度最深的)。所以,我们需要把所在的这棵Splay翻转过来。

(粗的是重链,y是原来的根)

翻转前:                                                                      翻转后:

 

这时候x才真正变成了根。

代码:

void mroot(int x){access(x);Splay(x);pushreverse(x);
}




link操作:

这个操作的作用是连接两棵LCT。对于link(u,v),表示连接u所在的LCT和v所在的LCT;

link实现的方式:

很简单,只需要先mroot(u),然后记录T[u].fa=v就可以了,就是把一个Splay森林连到另一个上。

代码:

void link(int u,int v){mroot(u);T[u].fa=v;
}




cut操作:

         这个操作的作用是分离出两棵LCT。

代码:

void cut(int u,int v)mroot(u);   //先把u变成根access(v);Splay(v);    //连接u、vpushdown(v);     //先下传标记T[u].fa=T[v].ch[0]=0;//v的左孩子表示v上方相连的重链//update(v);  //记得维护信息
}




这些就是LCT的基本操作。我推荐几个LCT的练习题:


bzoj2049 SDOI2008洞穴勘探

模板题,只需要linkcut,然后询问连通性。题解:

http://blog.csdn.net/saramanda/article/details/55210235


bzoj2002 HNOI2010弹飞绵羊

模板题,需要link和询问某点到根的路径长度。题解:

http://blog.csdn.net/saramanda/article/details/55210418


bzoj3669 NOI2014魔法森林

LCT的综合应用。题解:

http://blog.csdn.net/saramanda/article/details/55250852

这篇关于LCT(Link-Cut Tree)详解(蒟蒻自留地)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/314089

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

K8S(Kubernetes)开源的容器编排平台安装步骤详解

K8S(Kubernetes)是一个开源的容器编排平台,用于自动化部署、扩展和管理容器化应用程序。以下是K8S容器编排平台的安装步骤、使用方式及特点的概述: 安装步骤: 安装Docker:K8S需要基于Docker来运行容器化应用程序。首先要在所有节点上安装Docker引擎。 安装Kubernetes Master:在集群中选择一台主机作为Master节点,安装K8S的控制平面组件,如AP

嵌入式Openharmony系统构建与启动详解

大家好,今天主要给大家分享一下,如何构建Openharmony子系统以及系统的启动过程分解。 第一:OpenHarmony系统构建      首先熟悉一下,构建系统是一种自动化处理工具的集合,通过将源代码文件进行一系列处理,最终生成和用户可以使用的目标文件。这里的目标文件包括静态链接库文件、动态链接库文件、可执行文件、脚本文件、配置文件等。      我们在编写hellowor

LabVIEW FIFO详解

在LabVIEW的FPGA开发中,FIFO(先入先出队列)是常用的数据传输机制。通过配置FIFO的属性,工程师可以在FPGA和主机之间,或不同FPGA VIs之间进行高效的数据传输。根据具体需求,FIFO有多种类型与实现方式,包括目标范围内FIFO(Target-Scoped)、DMA FIFO以及点对点流(Peer-to-Peer)。 FIFO类型 **目标范围FIFO(Target-Sc

019、JOptionPane类的常用静态方法详解

目录 JOptionPane类的常用静态方法详解 1. showInputDialog()方法 1.1基本用法 1.2带有默认值的输入框 1.3带有选项的输入对话框 1.4自定义图标的输入对话框 2. showConfirmDialog()方法 2.1基本用法 2.2自定义按钮和图标 2.3带有自定义组件的确认对话框 3. showMessageDialog()方法 3.1

脏页的标记方式详解

脏页的标记方式 一、引言 在数据库系统中,脏页是指那些被修改过但还未写入磁盘的数据页。为了有效地管理这些脏页并确保数据的一致性,数据库需要对脏页进行标记。了解脏页的标记方式对于理解数据库的内部工作机制和优化性能至关重要。 二、脏页产生的过程 当数据库中的数据被修改时,这些修改首先会在内存中的缓冲池(Buffer Pool)中进行。例如,执行一条 UPDATE 语句修改了某一行数据,对应的缓

OmniGlue论文详解(特征匹配)

OmniGlue论文详解(特征匹配) 摘要1. 引言2. 相关工作2.1. 广义局部特征匹配2.2. 稀疏可学习匹配2.3. 半稠密可学习匹配2.4. 与其他图像表示匹配 3. OmniGlue3.1. 模型概述3.2. OmniGlue 细节3.2.1. 特征提取3.2.2. 利用DINOv2构建图形。3.2.3. 信息传播与新的指导3.2.4. 匹配层和损失函数3.2.5. 与Super

树(Tree)——《啊哈!算法》

树 什么是树?树是一种特殊的图,不包含回路的连通无向树。 正因为树有着“不包含回路”这个特点,所以树就被赋予了很多特性。 一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点,那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。 一棵树有且只有一个根结点。 没有父结点的结点称为根结点(祖先)。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶