LCT(Link Cut Tree)学习小记

2023-10-28 11:32
文章标签 学习 link tree 小记 cut lct

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

动态树(Dynamic Tree)
之前我一直以为这是一种数据结构,最近才明白这是指一类问题。

在学习LCT之前首先要学习树链剖分。
树链剖分就是将一棵树划分成若干条链,用数据结构去维护每条链,复杂度为O(logN)。

树链剖分针对的是树的形状不会变的树,但是如果树的形状是会变的(即要支持将树分离、合并的操作),就需要用到LCT(Link Cut Tree)了。

LCT大概思路就是用splay去维护每一条链,同时支持以下操作
1、Access(x):将x到根节点的路径变成一条树链(p.s.Access是一切操作的基础)
2、MakeRoot(x):将x变成x所在的树的根节点
3、Link(x,y):在x与y之间连一条边
4、Cut(x,y):将x与y之间的边删掉

代码如下:
1、Access(x):将x到根节点的路径变成一条树链(p.s.Access是一切操作的基础)

void access(int x){for(int t=0;x;t=x,x=fa[x])splay(x),s[x][1]=t,update(x);
}

2、MakeRoot(x):将x变成x所在的树的根节点

void makeroot(int x){access(x),splay(x),rev[x]^=1;
}

3、Link(x,y):在x与y之间连一条边

void link(int x,int y){makeroot(x);fa[x]=y;
}

4、Cut(x,y):将x与y之间的边删掉

void cut(int x,int y){makeroot(x);access(y);splay(y);s[y][0]=fa[x]=0;update(y);
}

代码比较简单,读者自己理解。

这篇关于LCT(Link Cut Tree)学习小记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一:创建批处理文件并添加到PATH1

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,:本文主要介绍Go学习记录之runtime包的... 目录前言:一、runtime包内容学习1、作用:① Goroutine和并发控制:② 垃圾回收:③ 栈和

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

重新对Java的类加载器的学习方式

《重新对Java的类加载器的学习方式》:本文主要介绍重新对Java的类加载器的学习方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、介绍1.1、简介1.2、符号引用和直接引用1、符号引用2、直接引用3、符号转直接的过程2、加载流程3、类加载的分类3.1、显示

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Linux使用cut进行文本提取的操作方法

《Linux使用cut进行文本提取的操作方法》Linux中的cut命令是一个命令行实用程序,用于从文件或标准输入中提取文本行的部分,本文给大家介绍了Linux使用cut进行文本提取的操作方法,文中有详... 目录简介基础语法常用选项范围选择示例用法-f:字段选择-d:分隔符-c:字符选择-b:字节选择--c

TP-Link PDDNS服将于务6月30日正式停运:用户需转向第三方DDNS服务

《TP-LinkPDDNS服将于务6月30日正式停运:用户需转向第三方DDNS服务》近期,路由器制造巨头普联(TP-Link)在用户群体中引发了一系列重要变动,上个月,公司发出了一则通知,明确要求所... 路由器厂商普联(TP-Link)上个月发布公告要求所有用户必须完成实名认证后才能继续使用普联提供的 D

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

TP-LINK/水星和hasivo交换机怎么选? 三款网管交换机系统功能对比

《TP-LINK/水星和hasivo交换机怎么选?三款网管交换机系统功能对比》今天选了三款都是”8+1″的2.5G网管交换机,分别是TP-LINK水星和hasivo交换机,该怎么选呢?这些交换机功... TP-LINK、水星和hasivo这三台交换机都是”8+1″的2.5G网管交换机,我手里的China编程has