当前位置: 首页 > news >正文

【图论】树链剖分

本篇博客参考:

  • 【洛谷日报#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
}

相关文章:

【图论】树链剖分

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

Requests教程-17-请求代理设置

上一小节我们学习了requests解决乱码的方法&#xff0c;本小节我们讲解一下requests设置代理的方法。 代理基本原理 代理实际上指的就是代理服务器&#xff0c; 英文叫作proxy server &#xff0c;它的功能是代理网络用户去取得网络信息。形象地说&#xff0c;它是网络信息的中…...

python内置函数 G

python内置函数 G Python 解释器内置了很多函数和类型&#xff0c;任何时候都能使用。 G 名称描述getattr从对象中获取属性值。globals返回当前全局符号表的字典。 getattr(object, name) getattr(object, name) getattr(object, name, default) getattr() 是 Python 中…...

深入了解 Spring boot的事务管理机制:掌握 Spring 事务的几种传播行为、隔离级别和回滚机制,理解 AOP 在事务管理中的应用

&#x1f389;&#x1f389;欢迎光临&#xff0c;终于等到你啦&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;持续更新的专栏《Spring 狂野之旅&#xff1a;从入门到入魔》 &a…...

机械产品CE-MD认证测试项目介绍

机械产品CE-MD认证测试项目介绍 一、引言 随着欧洲市场的日益开放和全球化进程的加速&#xff0c;越来越多的机械产品进入欧洲市场。为确保这些产品的安全性和符合性&#xff0c;欧洲联盟&#xff08;EU&#xff09;引入了CE认证制度。同时&#xff0c;对于医疗器械类产品&…...

金融知识分享系列之:MACD指标精讲

金融知识分享系列之&#xff1a;MACD指标精讲 一、MACD指标二、指标原理三、MACD指标参考用法四、MACD计算步骤五、MACD分析要素六、根据快线DIF位置判断趋势七、金叉死叉作为多空信号八、快线位置交叉信号九、指标背离判断行情反转十、差离值的正负十一、差离值的变化十二、指…...

王道c语言-100元有几种换法

Description 一张面值100元的人民币换成10元、5元、2元和1元面值的票子。要求换正好40张&#xff0c;且每种票子至少一张。问&#xff1a;有几种换法&#xff1f; #include <stdio.h> int main() {int count 0;int i, j, t, k, ret 0;for (i 1; i < 37; i) {for …...

c++野指针如何处理?

什么是野指针&#xff1f; 野指针指向一个已删除的对象或未申请访问受限内存区域的指针。与空指针不同&#xff0c;野指针无法通过简单地判断是否为NULL避免&#xff0c;而只能通过养成良好的编程习惯来尽力减少&#xff0c;对野指针进行操作很容易造成程序错误。 野指针产生…...

关于大根堆,set重载运算符

题目描述 \,\,\,\,\,\,\,\,\,\,制定合理的日程能够帮助利用好时间进行加训&#xff0c;加训和加训。 \,\,\,\,\,\,\,\,\,\,新学期开始了&#xff0c;应该好好学习了&#xff01;凌晨两点整&#xff0c;加睡失败的你在为新一天的各项重要事件制定闹钟。 \,\,\,\,\,\,\,\,\,\, \,…...

Algae c++

描述 问题陈述 池塘中藻类的发展情况如下。 假设年初i水藻的总重量为xi​克。对于 i≥2000&#xff0c;下列公式成立&#xff1a; xi1​rxi​−D 给你r、D和x2000​。请依次计算 x2001​、...、x2010​ 并打印出来。 输入描述 输入内容由标准输入法提供&#xff0c;格式…...

开发常用的一些工具总结

开发常用的一些工具总结 记录一些常用的开发软件. Android 开发相关 : Android studio 安卓开发者必备的编辑器,也是我用过最好用的编辑器.还可以用来写JNI 和C.Android studio 插件 : GsonFormatLeakCanary 其他 VS Code :轻量级的开发工具,插件非常多,很好用,但是上手难度…...

k8s Yaml语法解析

YAML是一个类似 XML、JSON 的标记性语言。它强调以数据为中心&#xff0c;并不是以标识语言为重点。因而YAML本身的定义比较简单&#xff0c;号称"一种人性化的数据格式语言"。 YAML的语法比较简单&#xff0c;主要有下面几个&#xff1a; 1、大小写敏感 2、使用缩进…...

【晴问算法】提高篇—动态规划专题—最长公共子序列

题目描述 现有两个字符串s1​​​​与s2​&#xff0c;求s1​​​​与s2​​​​的最长公共子序列的长度&#xff08;子序列可以不连续&#xff09;。 输入描述 第一行为字符串s1​​&#xff0c;仅由小写字母组成&#xff0c;长度不超过100&#xff1b; 第一行为字符串s2​​​…...

Greetings

Problem - 1915F - Codeforces 题意 给一些(l,r)找到所有能够包含(l,r)的数目 引入 也就是找逆序对个数 要用到归并排序中的思想&#xff1a; //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&#xff08;SSM部分安装过&#xff09;3.初始化前端工程1.创建一个文件夹 springboot_vue2.创建vue项目1.在刚才创建的文件夹下打开命令行&#xff0c;使用脚手架搭建项目2.选择手动配置3.选择三个4.选择vue35.选择路由模式6.选择包管理方…...

elementui el-table表格自动循环滚动【超详细图解】

效果如图 1. 当表格内容超出时&#xff0c;自动滚动&#xff0c;滚动到最后一条之后在从头滚动。 2. 鼠标移入表格中&#xff0c;停止滚动&#xff1b;移出后&#xff0c;继续滚动。 直接贴代码 <template><div><div class"app-container"><e…...

关于学习的一点粗浅见解

我们学习的每一个领域&#xff0c;大多都有着宽泛的知识面&#xff0c;那在学习过程中&#xff0c;我们是应该一开始就专钻一个方向(即深度)&#xff0c;还是应该先扩展知识面(即广度)&#xff1f;个人认为&#xff0c;应该先扩展知识面宽度&#xff0c;然后再精研某个方向&…...

第19节 Node.js Express 框架

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

MFC内存泄露

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

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

云原生玩法三问:构建自定义开发环境

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

Qt的学习(一)

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

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...

用js实现常见排序算法

以下是几种常见排序算法的 JS实现&#xff0c;包括选择排序、冒泡排序、插入排序、快速排序和归并排序&#xff0c;以及每种算法的特点和复杂度分析 1. 选择排序&#xff08;Selection Sort&#xff09; 核心思想&#xff1a;每次从未排序部分选择最小元素&#xff0c;与未排…...

【技巧】dify前端源代码修改第一弹-增加tab页

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