首页 > 其他分享 >树链剖分

树链剖分

时间:2025-01-17 18:00:18浏览次数:1  
标签:两遍 剖分 线段 dfs 树链 数据结构

原理:将树以一种划分方式分成若干条链,转换为区间,再用数据结构维护
一般形式:两遍dfs初始化+数据结构(线段树/树状数组)
解决的问题:各种树上区间操作(维护的东西越多,解决问题的范围就越大)

两遍dfs维护的:
$fa$[ ](父节点)
$son$[ ](重儿子)
$dep$[ ](深度)
$siz$[ ](子树大小)
$seg$[ ](树中点在数据结构(如线段树)中编号)
$rev$[ ](数据结构中点在树中编号)
$top$[ ](重链头)
轻重边的一些性质:
1.如果(u, v)为轻边,则size[v] <= size[u] / 2。
2.从根到某一点v的路径上,轻边个数不多于O(logn)。
3.称某条路径为重路径(重链),当且仅当它全部由重边组成,一个点也算一条重路径。那么对于每个点到根的路径上都有不超过O(logn)条轻边和O(logn)条重路径。
4.每个点都在且仅在一条重路径上,每条路径一定是一条从根结点方向向叶结点延申的深度递增的路径。

标签:两遍,剖分,线段,dfs,树链,数据结构
From: https://www.cnblogs.com/hirasawayuii/p/18677473

相关文章

  • 曲面的三角剖分
    目录曲面上的三角形曲面的三角剖分不是三角剖分的例子曲面上的三角形设Σ\SigmaΣ是E......
  • 【C++动态规划 数学】1039. 多边形三角剖分的最低得分|2130
    本文涉及知识点C++动态规划数学LeetCode1039.多边形三角剖分的最低得分你有一个凸的n边形,其每个顶点都有一个整数值。给定一个整数数组values,其中values[i]是第i个顶点的值(即顺时针顺序)。假设将多边形剖分为n-2个三角形。对于每个三角形,该三角形的值......
  • 树链剖分
    更新日志2025/01/07:开工。概念树链剖分,将树剖分成多个不相交的链。视情况,我们选择合适的方式进行剖分。我们往往可以借此解决“路径权值修改”问题,或者对启发式合并有所帮助。方式通常的,对于每个节点,我们视自己的需求,每次选择最优的一个子节点,加入其链,而其他子节点分......
  • 链剖分总结
    来解决树上DS问题。因为没有能够直接高效维护树型结构的DS,于是把树剖分成链,然后拿序列上的DS去维护每一条链的信息。树链剖分有很多种:轻重链剖分,长链剖分,虚实链剖分。轻重链剖分这里是轻重链剖分。常数很小。其实不一定要用线段树维护,但用线段树维护是最常见的。支持换根,路......
  • 【知识】树链剖分
    树链剖分思想:将一颗树转换成一段序列,满足树中任意一条路径$\Leftrightarrow$不超过\(\logn\)段区间概念:重儿子​ 一个点的重儿子为它的儿子的子树节点个数最多的那个点。​ 如有多个,任选一个。轻儿子不是重儿子的都为轻儿子重边与重儿子相连的边轻边与......
  • 重链剖分, 树上路径问题大杀器
    重链剖分,树上路径问题大杀器首先,什么是树链剖分数组,要进行修改查询是非常方便的,一眼线段树.但是树并不是.看一下我们目前已有的树上修改查询技术.树上差分只能修改,最后才能查询,不然就只能很慢的单点查询,DFS序+线段树只能进行子树操作,不能进行路径操作.......
  • [OI] 树链剖分
    学的时候比较朦胧,现在不朦胧了,所以写一下讲解重儿子:一个节点的子树大小最大的儿子轻儿子:非重儿子重链:节点->重儿子->重儿子..这样的链AbeautifulTree蓝线为重链可以发现,树上的所有节点一定属于且仅属于一个重链首先要知道如何找重链这很简单,可以通过一遍DFS......
  • [学习笔记]树链剖分(简易版) 及其LCA
    树链剖分先讲解一下一些基础定义(都是在树上)重儿子:一个节点中所有儿子中子树大小最大的一个儿子(每个节点最多有一个重儿子)轻儿子:一个节点除重儿子外所有的节点重链:若干个重儿子组成的链链顶:一条链中深度最小的节点以下图为例子(红色连续线段为重链)对于节......
  • 树链剖分
    由于是在树上搞的ds所以考察数据结构本身性质偏多,需大力注重细节。思想考虑将一颗树的链划分成若干个区间进行维护。这种划分方式叫做剖分。约束一颗有根树(有时要求换根但不是真正换根)每个点恰好包含在一条剖出的链中(若被多条链同时包含则需要同时维护多条链,修改多余......
  • 树链剖分
    原理:将一棵树剖分成一条条的链,从而降低时间复杂度首先会一个线段树,书完成剖分后,用来维护每一条的信息。#include<bits/stdc++.h>typedefintintt;#defineintlonglong#definelck<<1#definerck<<1|1constintM=2e6+10;usingnamespacestd;intn,m,ans......