树链剖分

### 简介 毒瘤的出题人把序列问题出到树上了。 ~~哪天出到仙人掌上就真的写不动了。~~ ### 其他题单 ### [数据结构 Part I](https://www.luogu.com.cn/training/232233) ### [数据结构 Part II](https://www.luogu.com.cn/training/245599) ### [数据结构 Part III](https://www.luogu.com.cn/training/294973) ### [数据结构 Part IV](https://www.luogu.com.cn/training/245598) ### [数据结构 Part V](https://www.luogu.com.cn/training/298198) ### 关于树链剖分 树链剖分是指一种对树进行划分的算法，它先通过不同的剖分方式将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、BST、SPLAY、线段树等）来维护每一条链 严格来讲，树链剖分（链剖分）分为：`轻重链剖分`（简称`重链剖分`），`长链剖分`，`虚实链剖分`（简称`实链剖分`或`LCT`）。其中重链剖分一般是我们口中的`树剖`，因常数小和树上的优良性质而著称，长链剖分其实不太常见，有些神仙题拿它优化 DP，而 LCT 则经常可以维护一些奇奇怪怪的东西（我不会，别问我） ### 对比 & 原理 - 重链剖分 剖分的原理是把节点个数最多的儿子当做重儿子 - 长链剖分 剖分的原理是把深度最深的儿子当做重(长)儿子，可以 $\mathcal{O}(1)$ 求 $k$ 级祖先 - 实链剖分 选择一个儿子作为重儿子，把连接这两个节点的边作为重边，连接其他儿子的边作为轻边，注意重儿子是可以不断变化的，因此在整棵树中的重链和轻链也是在不断变化的 ### [轻重链剖分简介](https://www.luogu.com.cn/blog/205125/shu-lian-pou-fen-shu-pou) ### 重链剖分模板 [P3384 【模板】轻重链剖分/树链剖分](https://www.luogu.com.cn/problem/P3384) 下面的题目树剖可能只是一种解法，也会存在不用树剖的更优解法，但用树剖肯定是能做的 - [P3379 【模板】最近公共祖先（LCA）](https://www.luogu.com.cn/problem/P3379) 树剖求LCA - [P3128 [USACO15DEC]Max Flow P](https://www.luogu.com.cn/problem/P3128) 树剖增加两点间权值+访问最大值 - [P3258 [JLOI2014]松鼠的新家](https://www.luogu.com.cn/problem/P3258) 树剖的简单变形 - [P2590 [ZJOI2008]树的统计](https://www.luogu.com.cn/problem/P2590) 树剖修改，求和，求最大值 #### 点权转边权 不会？可以去看看[这个](https://www.luogu.com.cn/blog/ShadderLeave/solution-p3038) - [P3038 [USACO11DEC]Grass Planting G](https://www.luogu.com.cn/problem/P3038) 点权转边权的简单应用 - [P2420 让我们异或吧](https://www.luogu.com.cn/problem/P2420) - [P1967 [NOIP2013 提高组] 货车运输](https://www.luogu.com.cn/problem/P1967) 最大生成树(然而这题没有森林数据)+树剖求两点间最小值 - [P2245 星际导航](https://www.luogu.com.cn/problem/P2245) 最小生成树+处理森林+树剖求两点间最大值 --- 建议学过重链剖分再来看 ### 长链剖分模板 [P5903 【模板】树上 k 级祖先](https://www.luogu.com.cn/problem/P5903) ### 性质 1. 任意节点 $u$ 的第 $k$ 级祖先 $v$ 所在链的长度一定大于 $k$ 2. 任意节点到达根节点经过的长链数最多是 $ \sqrt{n} $ #### 1. 长链剖分剖分可以 $\mathcal{O}(n \log n)$ 预处理，$\mathcal{O}(1)$ 在线查询 $k$ 级祖先 记 $\mathcal{O}(n \log n)$-$\mathcal{O}(1)$ 为预处理时间复杂度和单次查询时间复杂度 重链剖分 $\mathcal{O}(n)$-$\mathcal{O}(\log n)$ 树上倍增 $\mathcal{O}(n \log n)$-$\mathcal{O}(\log n)$ 事实上，想要单次查询做到 $\mathcal{O}(1)$，这些做法显然不行，对于重链剖分，它已经很优了，无法优化。对于树上倍增，二进制转换永远有 $\log n$，那么还有一种就是提前暴力预处理所有情况，预处理时间和空间都是 $\mathcal{O}(n^2)$ 显然无法接受 那么我们可以综合以上思想，折中选择根号，即用类似倍增的方法 $\mathcal{O}(n \sqrt n)$ 预处理每 $\sqrt n$ 级祖先，然后处理 $\sqrt n$ 以内的祖先，这样就可以单次查询 $\mathcal{O}(1)$ 但是显然这是一种 $\mathcal{O}(n \sqrt n)$-$\mathcal{O}(1)$ 的算法，仅仅为了单次查询的一只 $\log n$，却付出了 $\mathcal{O}(n \sqrt n)$ 的预处理代价，其实还是不太优 这时候该长链剖分出场了，我们有类似重链剖分的方法维护，时空复杂度仍为 $\mathcal{O}(n)$ ，这样有什么用？这样做以后，我们的树上倍增只用跳最大的一步。 显然这个最大的一步的长度必定大于 $k/2$，于是我们跳到的那个点往下的长链长度至少就有 $k/2$，所以就算 $k$ 级祖先不在这条长链上，也一定可以从我们跳到的那个点的已知信息里直接求到 于是我们只要再预处理出对于每个数，它最大的二进制位是多少，我们就可以 $\mathcal{O}(1)$ 地求出任意一个点的$k$级祖先了。 不过只有在询问个数很多很多时才能看出它快，~~所以一般没啥用~~ #### 2. 长链剖分可以把维护子树中 只与深度有关 的信息优化到线性 长链剖分优化 DP 的实现方式就是，长链剖分后，在维护信息的过程中，先 $\mathcal{O}(1)$ 继承重儿子的信息，再暴力合并其余轻儿子的信息。 在统计以深度为下标的时候，重链剖分优化一般可以到 $\mathcal{O}(n\log n)$，因为暴力统计**轻边 $\log n$ 条**，而长链剖分可以到 $\mathcal{O}(n)$，因为**所有子树**被作为轻儿子暴力统计的代价和是 $\mathcal{O}(n)$ 的。而被作为重儿子统计的代价，因为父亲直接继承了它的数组，所以每个点是 $\mathcal{O}(1)$ 的，最终就是 $\mathcal{O}(n)$ #### 相关题目： - [CF1009F Dominant Indices](https://www.luogu.com.cn/problem/CF1009F) - [CF208E Blood Cousins](https://www.luogu.com.cn/problem/CF208E) - [P3899 [湖南集训]更为厉害](https://www.luogu.com.cn/problem/P3899) - [P5384 [Cnoi2019]雪松果树](https://www.luogu.com.cn/problem/P5384) - [P5904 [POI2014]HOT-Hotels 加强版](https://www.luogu.com.cn/problem/P5904) - [CF860E Arkady and a Nobody-men](https://www.luogu.com.cn/problem/CF860E) - [P4292 [WC2010]重建计划](https://www.luogu.com.cn/problem/P4292) - [CF526G Spiders Evil Plan](https://www.luogu.com.cn/problem/CF526G) --- #### 前置芝士：Splay 建议学过重链剖分再来看 ### LCT模板 [P3690 【模板】动态树（Link Cut Tree）](https://www.luogu.com.cn/problem/P3690) #### 学习LCT [1](http://blog.csdn.net/wxjor/article/details/79512079) [2](https://www.cnblogs.com/flashhu/p/8324551.html) ### LCT支持什么 通俗来讲，有这些： - 查询两点之间路径上的信息（如和、异或和等） - 连边 - 删边 - 动态维护连通性