当前位置: 首页 > 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;然后再精研某个方向&…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

Python环境安装与虚拟环境配置详解

本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南&#xff0c;适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者&#xff0c;都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...

高抗扰度汽车光耦合器的特性

晶台光电推出的125℃光耦合器系列产品&#xff08;包括KL357NU、KL3H7U和KL817U&#xff09;&#xff0c;专为高温环境下的汽车应用设计&#xff0c;具备以下核心优势和技术特点&#xff1a; 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计&#xff0c;确保在…...