树你应该懂的吧o( ̄︶ ̄)o
学习树链剖分之前需要先学习:$dfs$、线段树(当然大佬们用树状数组代替线段树也可以O(∩_∩)O),据说一名普及+的$oier$应该都会呀
先来了解树链剖分的用处
已知一棵包含$N$个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作:
操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
操作3: 格式: 3 x z 表示将以x为根节点的子树内所有节点值都加上z
操作4: 格式: 4 x 表示求以x为根节点的子树内所有节点值之和
如果直接暴力的话,肯定会TLE(废话)。所以这时候,树链剖分闪亮登场。
什么是树链剖分
一种算法(废话),它通过分轻重边把树分割成很多链,然后利用某种数据结构维护这些链(比如上文提到的线段树、树状数组等)但前提是这种数据结构支持动态修改(你别给我整个RMQ)。本质上是一种暴力算法。
PS:树剖的复杂度约为$O(nlog^2n)$
树链剖分的基本概念
名称 | 概念 |
---|---|
重儿子 | 父亲节点的所有儿子中子节点数目最多(sz最大)的节点 |
轻儿子 | 父亲节点除了重儿子以外的儿子 |
重边 | 父亲节点和重儿子连成的边 |
轻边 | 父亲节点和轻儿子连成的边 |
重链 | 由多条重边连成的路径 |
轻链 | 由多条轻边连成的路径 |
没看懂?没关系,结合下面这张图:(红色的边代表重边,黑色的边代表轻边,红色的节点代表重儿子,黑色的节点代表轻儿子)
PS:这里默认树根也是重儿子。
上图的重链有:1-4,3-6。
变量声明
1 | ll fir[MAXN],nxt[MAXN*2],son[MAXN*2],w[MAXN*2],tot; |
名称 | 作用 |
---|---|
$fir_x$ | 关于$x$的最后一条边编号 |
$nxt_x$ | 关于$x$的上一条边编号 |
$son_x$ | 第$x$条边的连向 |
$w_x$ | 其实没啥用,打着习惯了 |
$a_x.ls$ | 编号为$x$的节点的左儿子 |
$a_x.rs$ | 编号为$x$的节点的右儿子 |
$fa_x$ | 编号为$x$的节点的父亲 |
$c_x$ | 编号为$x$的节点的重儿子 |
$rk_x$ | 当前$dfs$标号在树中所对应的节点的编号 |
$top_x$ | 编号为$x$的节点所在链的顶端节点编号 |
$id_x$ | 编号为$x$的节点$dfs$后的新编号 |
$dep_x$ | 编号为$x$的节点的深度 |
$sz_x$ | 以编号为$x$的节点为根的子树的节点个数 |
树链剖分的实现
第一次$dfs$求出每个节点的重儿子、父亲、深度、子树大小。
PS:如果一个点的多个儿子所在子树大小相等且最大,那随便找一个当做它的重儿子就好了,叶节点没有重儿子,非叶节点有且只有一个重儿子。
1 | inline void dfs1(ll x,ll f,ll deep){ |
操作完以后应该是下图:
第二次$dfs$求出每个节点的链顶端节点、新编号、$dfs$编号对应的节点编号。
1 | inline void dfs2(ll x,ll ttop){ |
操作完以后应该是下图:
线段树等数据结构的维护
接下来就是线段树、树状数组等数据结构的维护了,具体使用哪种数据结构因题目而异,这里提供模板题(上文介绍的题目)所使用的线段树(区间修改、区间询问)。
1 | inline void pushup(ll x){ |
根据题目需要添加操作
就比如上文的题目中还要求的操作:
- 操作1: 格式: 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
- 操作2: 格式: 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
与操作3、操作4不同,这里要求的是一条路径上的节点,而没有告诉我们节点的编号,所以,我们这时要求出节点编号:
1 | inline ll Query(ll x,ll y){ |
当然,还有一个操作是非常常用的,那就是求lca(最近公共祖先)。
1 | inline ll lca(ll x,ll y){ |
模板题代码
对对对,就是上文提到的题目。
1 | #include<bits/stdc++.h> |
完美撒花✿✿ヽ(°▽°)ノ✿