【图论】树链剖分
本篇博客参考:
- 【洛谷日报#17】树链剖分详解
- Oi Wiki 树链剖分
文章目录
- 基本概念
- 代码实现
- 常见应用
- 路径维护:求树上两点路径权值和
- 路径维护:改变两点最短路径上的所有点的权值
- 求最近公共祖先
基本概念
首先,树链剖分是什么呢?
简单来说,就是把一棵树分成很多条链,然后利用数据结构(线段树、树状数组)维护链上的信息
下面是一些定义:
- 重子结点:父亲结点的所有儿子结点中子树结点数目最多的结点称为重子结点
- 轻子结点:父亲结点的所有儿子中除了重子结点的其他结点称为轻子结点
如果某个结点是叶子结点,那么它既没有重子结点也没有轻子结点
- 重边:父亲结点和重子结点连成的边
- 轻边:父亲结点和轻子结点连成的边
- 重链:多条重边连接成的链
- 轻链:多条轻边连接成的链
落单的点也当做重链,那整棵树就会被分成若干条重链,类似这样:(图源Oi Wiki)
下面是一些变量声明:
fa[u]
结点 u 的父亲结点dep[u]
结点 u 的深度sz[u]
以结点 u 为根的子树的结点个数son[u]
结点 u 的重儿子top[u]
结点 u 所在链的顶端结点dfn[u]
结点 u 在 dfs 中的执行顺序,同时也是树链剖分后的新编号,可以理解为dfs序的映射id[u]
dfn 标号 u 对应的结点编号,有id[dfn[u]] == u
树链剖分的一些性质
- 重链开头的结点不一定是重子结点(因为每一个非叶子结点不管是重子结点还是轻子结点都有重边)
- 剖分时重链优先遍历,最后的 dfs 序中(也就是
dfn
数组),重链的 dfs 序时连续的,按 dfs 序排序后的序列就是剖分后的链 - 时间复杂度 O ( l o g n ) O(logn) O(logn)
代码实现
接下来需要实现树链剖分,也就是把每个结点划到一条链里,这通常是由两边 dfs 来实现的
第一遍 dfs
目的:处理 fa[u]
dep[u]
sz[u]
son[u]
void dfs1(int u, int father, int depth) // u: 当前结点 fa: 父结点 depth: 当前深度
{fa[u] = father; // 更新当前结点父结点dep[u] = depth; // 更新当前结点深度sz[u] = 1; // 子树大小初始化为1for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i]; // 子结点编号if (j == father) continue;dfs1(j, u, depth + 1);sz[u] += sz[j]; // 用子结点的sz更新父结点的szif (sz[j] > sz[son[u]]) son[u] = j; // 更新重子结点}
}
第二遍 dfs
目的:处理 top[u]
dfn[u]
id[u]
void dfs2(int u, int tt) // u: 当前结点 tt: 重链顶端结点
{top[u] = tt; // 更新当前结点所在重链顶端dfn[u] = ++ cnt; // 更新dfs序id[cnt] = u; // 更新dfs序的映射if (!son[u]) return; // 叶子结点 直接退出// 优先遍历重子结点 目的是保证链上各个结点的dfs序连续// 当前结点的重子结点和当前结点在同一条链上 所以链的顶端都是ttdfs2(son[u], tt); for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i]; // 子结点编号if (j == son[u] || j == fa[u]) continue; // 遇到重子结点或者父结点就跳过dfs2(j, j); // j点位于轻链顶端 它的top必然是本身}
}
常见应用
两遍 dfs 之后,就已经完成了树链剖分的操作,但是由于本人举一反三能力缺失根本不知道应该怎么用,所以后面再放几个常见的使用情况
路径维护:求树上两点路径权值和
这里做的是一个类似LCA的操作,如果两个结点不在同一条链上,就让深度更大的结点往上跳(每次只能跳一个结点,避免两个结点一起跳导致擦肩而过)直到跳到同一条链上,因为同一条链上的点 dfs 序是相邻的,所以可以直接在这条链上用数据结构计算权值和(下面的代码用的是线段树)
int sum(int x, int y) // xy表示待求的两点路径权值和
{int ans = 0;int tx = top[x], ty = top[y]; // tx ty分别表示x和y所在重链的顶端结点while (tx != ty) // 让x和y跳到同一条链上{if (dep[x] >= dep[y]) // x比y更深 让x先跳{ans += query(dfn[tx], dfn[x]); // query是线段树的区间求和函数x = fa[tx], tx = top[x]; // 让x跳到原先链顶端的父结点 更新tx}else{ ans += query(dfn[ty], dfn[y]); // query是线段树的区间求和函数y = fa[ty], ty = top[y]; // 让y跳到原先链顶端的父结点 更新ty}}// 循环结束 x和y终于到了同一条链 但是二者不一定是同一个结点 所以还需要计算两点之间的贡献if (dfn[x] <= dfn[y]) ans += query(dfn[x], dfn[y]);else ans += query(dfn[y], dfn[x]);return ans;
}
路径维护:改变两点最短路径上的所有点的权值
和上面的求最短路径权值和很像,都是先让两个点跳到同一条链上再进行计算
void update(int x, int y, int c) // 把x与y的最短路上所有点的权值都加上c
{int tx = top[x], ty = top[y];while (tx != ty){if (dep[tx] >= dep[ty]){modify(dfn[tx], dfn[x], c); // modify是线段树区间修改的函数x = fa[tx], tx = top[x]; // 让x跳到原先链顶端的父结点 更新tx}else{modify(dfn[ty], dfn[y], c); // modify是线段树区间修改的函数y = fa[ty], ty = top[y]; // 让y跳到原先链顶端的父结点 更新ty}}// 循环结束 x和y终于到了同一条链 但是二者不一定是同一个结点 所以还需要对两点之间的结点进行修改if (dfn[x] <= dfn[y]) modify(dfn[x], dfn[y], c);else modify(dfn[y], dfn[x], c);
}
求最近公共祖先
思路就是,如果两个点不在一条重链上,那就不断让深度大的结点往上跳,直到跳到同一条链上,那么深度较小的点就是LCA
int lca(int u, int v) // 求u和v的lca
{while (top[u] != top[v]) // 如果u和v不在同一条链上就一直让深度大的点往上跳{if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];else v = fa[top[v]];}return dep[u] > dep[v] ? v : u; // 深度小的结点就是lca
}
相关文章:

【图论】树链剖分
本篇博客参考: 【洛谷日报#17】树链剖分详解Oi Wiki 树链剖分 文章目录 基本概念代码实现常见应用路径维护:求树上两点路径权值和路径维护:改变两点最短路径上的所有点的权值求最近公共祖先 基本概念 首先,树链剖分是什么呢&…...

Requests教程-17-请求代理设置
上一小节我们学习了requests解决乱码的方法,本小节我们讲解一下requests设置代理的方法。 代理基本原理 代理实际上指的就是代理服务器, 英文叫作proxy server ,它的功能是代理网络用户去取得网络信息。形象地说,它是网络信息的中…...
python内置函数 G
python内置函数 G Python 解释器内置了很多函数和类型,任何时候都能使用。 G 名称描述getattr从对象中获取属性值。globals返回当前全局符号表的字典。 getattr(object, name) getattr(object, name) getattr(object, name, default) getattr() 是 Python 中…...

深入了解 Spring boot的事务管理机制:掌握 Spring 事务的几种传播行为、隔离级别和回滚机制,理解 AOP 在事务管理中的应用
🎉🎉欢迎光临,终于等到你啦🎉🎉 🏅我是苏泽,一位对技术充满热情的探索者和分享者。🚀🚀 🌟持续更新的专栏《Spring 狂野之旅:从入门到入魔》 &a…...
机械产品CE-MD认证测试项目介绍
机械产品CE-MD认证测试项目介绍 一、引言 随着欧洲市场的日益开放和全球化进程的加速,越来越多的机械产品进入欧洲市场。为确保这些产品的安全性和符合性,欧洲联盟(EU)引入了CE认证制度。同时,对于医疗器械类产品&…...

金融知识分享系列之:MACD指标精讲
金融知识分享系列之:MACD指标精讲 一、MACD指标二、指标原理三、MACD指标参考用法四、MACD计算步骤五、MACD分析要素六、根据快线DIF位置判断趋势七、金叉死叉作为多空信号八、快线位置交叉信号九、指标背离判断行情反转十、差离值的正负十一、差离值的变化十二、指…...
王道c语言-100元有几种换法
Description 一张面值100元的人民币换成10元、5元、2元和1元面值的票子。要求换正好40张,且每种票子至少一张。问:有几种换法? #include <stdio.h> int main() {int count 0;int i, j, t, k, ret 0;for (i 1; i < 37; i) {for …...
c++野指针如何处理?
什么是野指针? 野指针指向一个已删除的对象或未申请访问受限内存区域的指针。与空指针不同,野指针无法通过简单地判断是否为NULL避免,而只能通过养成良好的编程习惯来尽力减少,对野指针进行操作很容易造成程序错误。 野指针产生…...

关于大根堆,set重载运算符
题目描述 \,\,\,\,\,\,\,\,\,\,制定合理的日程能够帮助利用好时间进行加训,加训和加训。 \,\,\,\,\,\,\,\,\,\,新学期开始了,应该好好学习了!凌晨两点整,加睡失败的你在为新一天的各项重要事件制定闹钟。 \,\,\,\,\,\,\,\,\,\, \,…...
Algae c++
描述 问题陈述 池塘中藻类的发展情况如下。 假设年初i水藻的总重量为xi克。对于 i≥2000,下列公式成立: xi1rxi−D 给你r、D和x2000。请依次计算 x2001、...、x2010 并打印出来。 输入描述 输入内容由标准输入法提供,格式…...
开发常用的一些工具总结
开发常用的一些工具总结 记录一些常用的开发软件. Android 开发相关 : Android studio 安卓开发者必备的编辑器,也是我用过最好用的编辑器.还可以用来写JNI 和C.Android studio 插件 : GsonFormatLeakCanary 其他 VS Code :轻量级的开发工具,插件非常多,很好用,但是上手难度…...
k8s Yaml语法解析
YAML是一个类似 XML、JSON 的标记性语言。它强调以数据为中心,并不是以标识语言为重点。因而YAML本身的定义比较简单,号称"一种人性化的数据格式语言"。 YAML的语法比较简单,主要有下面几个: 1、大小写敏感 2、使用缩进…...
【晴问算法】提高篇—动态规划专题—最长公共子序列
题目描述 现有两个字符串s1与s2,求s1与s2的最长公共子序列的长度(子序列可以不连续)。 输入描述 第一行为字符串s1,仅由小写字母组成,长度不超过100; 第一行为字符串s2…...

Greetings
Problem - 1915F - Codeforces 题意 给一些(l,r)找到所有能够包含(l,r)的数目 引入 也就是找逆序对个数 要用到归并排序中的思想: //https://www.luogu.com.cn/problem/P1216 #include<iostream> #include<cstdio> #include<stack> #include…...
JS03-函数
函数 使用函数 // 函数声明function sayHi(){document.write(Hello!<br>)}for(let i 1; i < 6; i){// 函数调用sayHi()}函数封装 function getScore(arr){sum 0for( let i 0; i < arr.length; i){sum arr[i]}document.write(sum)}getScore([99, 66, 100])函数…...

MySQL | CRUD
目录 1. Create 2. Retrieve 2.1. SELECT列 2.1.1. 全列查询 2.1.2. 指定列查询 2.1.3. 查询字段为表达式 2.1.4. 为查询结果指定别名 2.1.5. 结果去重 2.2. WHERE条件 2.2.1. 年龄小于19的同学 2.2.2. id在2~3的同学 2.2.3. id为1和4的同学 2.2.4. 姓张的同学及张…...

【电路笔记】-MOSFET作为开关
MOSFET 作为开关 文章目录 MOSFET 作为开关1、概述2、MOSFET特性曲线2.1 截住区域2.2 饱和区域3、MOSFET作为开关的示例4、功率MOSFET电机控制5、P沟道MOSFET作为开关6、互补MOSFET作为开关电机控制器当 MOSFET 在截止区和饱和区之间工作时,MOSFET 是非常好的电子开关,用于控…...

SpringBoot+Vue项目(Vue3环境搭建 + 基础页面)
文章目录 1.项目基本介绍2.安装Node.js(SSM部分安装过)3.初始化前端工程1.创建一个文件夹 springboot_vue2.创建vue项目1.在刚才创建的文件夹下打开命令行,使用脚手架搭建项目2.选择手动配置3.选择三个4.选择vue35.选择路由模式6.选择包管理方…...

elementui el-table表格自动循环滚动【超详细图解】
效果如图 1. 当表格内容超出时,自动滚动,滚动到最后一条之后在从头滚动。 2. 鼠标移入表格中,停止滚动;移出后,继续滚动。 直接贴代码 <template><div><div class"app-container"><e…...
关于学习的一点粗浅见解
我们学习的每一个领域,大多都有着宽泛的知识面,那在学习过程中,我们是应该一开始就专钻一个方向(即深度),还是应该先扩展知识面(即广度)?个人认为,应该先扩展知识面宽度,然后再精研某个方向&…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...

云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Qt的学习(一)
1.什么是Qt Qt特指用来进行桌面应用开发(电脑上写的程序)涉及到的一套技术Qt无法开发网页前端,也不能开发移动应用。 客户端开发的重要任务:编写和用户交互的界面。一般来说和用户交互的界面,有两种典型风格&…...

边缘计算网关提升水产养殖尾水处理的远程运维效率
一、项目背景 随着水产养殖行业的快速发展,养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下,而且难以实现精准监控和管理。为了提升尾水处理的效果和效率,同时降低人力成本,某大型水产养殖企业决定…...
用js实现常见排序算法
以下是几种常见排序算法的 JS实现,包括选择排序、冒泡排序、插入排序、快速排序和归并排序,以及每种算法的特点和复杂度分析 1. 选择排序(Selection Sort) 核心思想:每次从未排序部分选择最小元素,与未排…...

【技巧】dify前端源代码修改第一弹-增加tab页
回到目录 【技巧】dify前端源代码修改第一弹-增加tab页 尝试修改dify的前端源代码,在知识库增加一个tab页"HELLO WORLD",完成后的效果如下 [gif01] 1. 前端代码进入调试模式 参考 【部署】win10的wsl环境下启动dify的web前端服务 启动调试…...