树分治
二月 04, 2024
树分治
树分治将分治技术运用到了树上，可以更好地维护两点间的路径问题，如果整棵树是一个序列，则可以看做是 CDQ 分治或者是整体二分。
主要思想就是递归的层数不超过 $\log$ 层，每层我们可以 $O(n)$ 遍历所有点，以执行其他操作。
点分治
点分治用于处理树上的路径问题。
一条路径如果指定了根节点，那可以被拆分为 $u \to root$ 和 $v \to root$ 两段进行讨论，点分治就是在这样的条件下产生的。
我们以 P3806 【模板】点分治 1 来讲解，这道题目要在 $O(n \log n)$ 的时间内求出是否有一条路径的长度等于 $k$。
如果选择了根，那么我们可以用桶在 $O(n)$ 时间内求出跨越根的路径有没有等于 $k$ 的，这个实现不难。
把根删除会得到若干棵子树，这些子树递归下去查找即可，但是这样做的时间复杂度是 $O(n^2)$ 的，因为我们有可能不断地选择一条链的端点作为根。
于是可以提出改进，每次选择的根是当前子树的重心，这样的话递归层数不超过 $\log$ 层，时间复杂度就是 $O(n \log n)$，但是记住每次清空的时候不能直接 memset，而需要记录修改了哪些位置上的值然后弹出修改才能保证时间复杂度，代码如下：
1 |
|
注意：一定要区分自己是哪棵子树的重心，代码中使用了颜色数组来记录。
例题 1
这道题相对于上一道题的不同是要求小于等于 $k$ 的路径条数，于是用树状数组维护加减查询即可。
代码如下，只是多了树状数组，时间复杂度 $O(n \log^2 n)$。
1 |
|
例题 2
这道题需要我们求出以每个节点开始的每条路径上的颜色种类之和，因为涉及到了较为复杂的路径查询，因此我们使用点分治解决它。
一条路径，要么是 $lca \to u$，要么是 $u \to lca \to v$，对于第一种情况，我们只需要开一个桶，存储每个点到我们枚举的点的颜色种类数就可以了。
对于第二种路径，如果当前枚举的点是 $u$，我们考虑对每种颜色分开计算贡献，如果某种颜色在 $u \to lca$ 的路径上出现过，那就会贡献所有 $v$（不和 $u$ 在同一棵 $lca$ 的子树内）的数量的答案。
否则我们另外开一个桶，当遍历到 $v$ 的时候如果 $a_v$ 在 $v \to lca$ 上只经过了一次，那么就让 $cnt_{a_v} \gets cnt_{a_v}+siz_v$，然后对于上面的第二种情况剩下的情况，就加上所有 $cnt_{p}$，其中 $p$ 不在 $u \to lca$ 上出现。
当然 $cnt$ 要减去当前子树的贡献。
最后不要忘了加上 $lca \to lca$ 的答案，以及清空我们用过的每个桶。
代码如下，不算难写：
1 |
|
点分治序
给定一个 $N$ 个结点的树，结点用正整数 $1 \sim N$ 编号。每条边有一个正整数权值。
用 $d(a,b)$ 表示从结点 $a$ 到结点 $b$ 的简单路径的距离。其中要求 $a<b$。将这 $\frac {N(N-1)}{2}$ 个距离从大到小排序，输出前 $M$ 个距离值。
如果按照点分治的顺序来加点到某个序列里面，那么这个序列的长度是 $O(n \log n)$ 的，并且每个点能够与之配对的点都在一个区间里面，即 $dis_{u,v}=dis_u+dis_v-2 \times dis_{\operatorname{lca}(u,v)}$
于是我们直接可以用超级钢琴题目的思路来解决，直接用 ST 表从堆里面取出 $M$ 个距离值，然后输出即可。
时间复杂度为 $O(n \log n \log k)$。
1 |
|
边分治
简单提一下，就是砍掉某条边，然后分治计算，但是这样的话对于菊花图来说时间复杂度仍然是 $O(n^2)$ 的，于是我们可以用多叉树转二叉树的方法转成类似线段树的样子，时间复杂度就正确了。
常数肯定比点分治大，也不推荐这种写法。
点分树
用于动态维护点分治的信息，通常会有强制在线、点权/边权修改等操作。
构建
我们考虑把整棵树进行重构，具体而言，设当前这棵树选择了 $pos$ 作为重心，划分成了 $T_1,T_2,T_3,\dots,T_k$ $k$ 棵子树，那么 $pos$ 在点分树上的儿子就是这 $k$ 棵子树选择的重心。
容易发现，这样构造出来的点分树的树高是 $O(\log)$ 级别的，因此很多并不太正确的暴力在点分树上执行操作都能得到较好的时间复杂度。
特别注意：点分树上如果 $u \to v \to w$ 不代表 $u$ 是 $v$ 在原树的祖先，$u \to w$ 在原树的距离也不能使用 $\operatorname{dis}(u,v)+\operatorname{dis}(v,w)$ 得到。
每次涉及到修改点权的时候就暴力跳祖先进行维护，如果是修改边权，就考虑边权变成点权之后再维护信息，时间复杂度通常是 $O(n \log n \times T)$，$T$ 是维护一次的时间复杂度，如果使用线段树等数据结构就是 $\log^2$ 的。
例题 1
这道题因为有点权的修改和路径的查询，所以考虑点分树处理。
一条路径可能会被划分为 $u \to lca$ 加上 $lca \to v$ 两个部分，因此我们根据路径的这个性质开始处理。
具体的，对于每个节点我们都需要维护一个它在点分树上的所有后代（包括本身）到它父亲的距离之和，这个距离可以使用倍增在原树上计算，并且我们可以维护一个平衡树轻松 $O(\log^2)$ 维护这个操作。
然后因为上面路径的性质，一个节点还需要维护它在点分树上的儿子节点中到它距离最远的两个（类似于 dp 树的直径），这个我们可以用平衡树来存储所有儿子的子树中到它距离最远的节点。（每个儿子的子树只存一个，避免路径重复计算）
最后用一个全局平衡树维护答案即可。
为了常数，程序中使用了可删堆来代替平衡树，时间复杂度总的就是 $O(n \log^2 n)$，并且要记得判断所有灯都开启的情况。
1 |
|
例题 2
定义分治块 $x$ 为点分树上以 $x$ 为根的子树的节点集合。
与上一道题不同的是，这道题是维护一个距离信息，而不是某条链的信息，我们依然可以考虑点分治。
因为不是维护链的信息，所以实现起来要简单许多，首先对于 $pos$ 节点来说，建立两棵线段树，一棵维护 $pos$ 的点分树子树内距离 $pos$ 节点为 $k$ 的点权和，一棵维护点分树子树内距离 $fa_{pos}$（点分树上的父亲）为 $k$ 的点权和。
修改是容易的，只需要在点分树上暴力跳父亲就可以了，考虑查询。
首先要加上当前点分树子树内距离 $pos$ 不超过 $v$ 的点权和，此时还有一些节点没有考虑，这些节点到 $pos$ 的路径一定经过了 $pos$ 在点分树上的祖先，考虑枚举祖先，设枚举到了 $y$，$y$ 往 $pos$ 走一步（下级祖先）是 $x$。
那么我们要加上所有经过 $y$ 到 $pos$ 的节点的点权和，答案就要加上 $y$ 子树对 $pos$ 的贡献，也就是 $0 \sim v-\operatorname{dis}(y,pos)$ 下标的和，这样的话我们算重复了一部分，那一部分并不需要经过 $y$ 到达 $pos$，但它们一定在 $x$ 及其子树内，于是减去 $x$ 的那棵维护点分树子树内距离 $fa_{pos}$（点分树上的父亲）为 $k$ 的点权和的线段树上 $0 \sim v-\operatorname{dis}(y,pos)$ 下标的和就可以了。
时间复杂度是 $O(n \log^2 n)$，空间复杂度卡满同阶。
1 |
|
总结
点分树的运用一般都是每个节点维护当前节点的点分树的子树内所有节点对于它的一些信息，和对于它在点分树上的父亲的一些信息。
涉及到链相关的询问，一般都是剖分成 $u \to lca,lca \to v$ 的信息进行合并处理。
涉及到层数/深度相关的询问，一般都是利用一些区间的数据结构处理，并且还需要小小的容斥一下，即上文”经过 $y$ 到达 $pos$ 的节点“，因为 $x$ 内的节点已经处理过了，删除掉 $x$ 子树对于答案的贡献即可。
点分树转化成普通的链的情况就是线段树，我们可以思考成树上的分治（本质也是如此）。
查看评论