点分治讲解

时间圣使·凡 · 2023-07-15 20:13:23 · 个人记录

\color{white} 建议学习的部分前置知识。

点分治所在的知识体系

如图所示点分治属于树上分治的一种。

而树上分治指的是对树形结构的数据进行分治。

本次讲解主要针对点分治。

点分治的一些概念性的东西

• 本质：点分治实际上就是不断将一棵树拆成多颗子树进行数据处理，并不断进行。
• 过程：将一颗无根树变为有根树，然后递归处理每一颗存在根节点的儿子的子树。
• 优化&一些计算方法：
  • 优化：以重心为根节点，可以证明这样的话递归深度最坏为 O _{(logN)}。
  • 计算方法：①（常用）每次走完一颗子树将有用信息存下来，然后在走下一颗子树的时候计算和记录的之前的信息贡献②先计算一个点所有子节点之间的贡献，再减去来自同一颗子树的部分
• 适用范围：对于一类统计树上路径信息（大规模 \color{white}~~，小规模一般暴力都能过吧……~~ ）（比如距离 \leq k 的点对数量, \mod m 意义下最长路径）等，可以考虑使用点分治。
• 效率：高效，能在 O_{(Nlog^{2}(N))} 的复杂度内查询所有路径信息。

点分治的大致框架

• 将树上路径分为两类，一类为经过根节点，一类为不经过根节点。
  • 第一类是核心部分，该部分统计方法因题而异。
  • 第二类则是将根节点的子树作为新的树递归下去计算。（可以理解为删除根节点，在剩下的所有子树上重新寻找合适的根节点并进行第一类的计算后，重复第二类操作）

关于树的重心：贴心的老师已经为不清楚的同学准备好了讲解文案，我们一起来阅读一下。

传送门

例题1：P4178 Tree

题目大意：

定一棵 n 个节点的带权树，定义 (u,v) 两点间距离为 u,v 两点间唯一路径上所有边权之和。

再给定一个正整数 K，求有多少对节点 (u,v) 满足两点距离不超过 K。 n \leq 40000 ， K \leq 20000。

解析：

题中的 n 个点虽然构成树，但没有明确的根节点,即为无根树。

我们将重心作为树的根节点，将其变为有根树（至于为什么将重心作为根节点，原因在下面解释）。

对于存在的路径，将路径拆分为多段，每段路径将不在根节点的同一颗子树上。这样才能正确计算距离，不然在同颗子树上会出现路径重合从而得出错误路径。

对于拆开的路径，我们可以用 d 数组表示，其中 d_{x} 表示 x 到根节点 root 的距离。

用 b_{x}表示节点 x 属于根节点 root 的哪一颗子树。

于是，对于两个节点 x 和 y，需要满足的条件便是

• b_{x}{=}\mathllap{/\,}b_{y}
• d_{x}+d_{y} \leq K

对于需要求的核心第一类路径，也可以使用大减小的方式，由于不实用，不做赘述(唯一的优点是数组用得少)。该方法代码在这。

实际程序有两种常见方式 （注意前面提及的路径计算多种方式与此多种程序实现方式不同，路径计算方式只是某些细节上的区别，是基于程序实现上的细节）：

方法一：树上直接统计

容我搬运一发老师的讲解谢谢

设根节点 root 的子树为 s_{1},s_{2},s_{3}……。对于 s_{i} 上的每个节点，把在子树 s_{1},s_{2},s_{3}……s_{i-1} 中满足d_{x}+ d_{y} \leq K的节点y加到答案中即可。

可以建立一个树状数组，一次处理每棵子树 s_{i}。

1、对 s_{i} 中的每个节点，查询 距离 \leq K-d_{x} 的节点数，加到答案数量中

2、对 s_{i} 中的每个节点，更新树状数组，对应的距离的节点数+1

上述步骤先处理第1步（一棵子树处理完），然后再处理第2步，保证节点对不在同一子树上。

值得注意的是，树状数组的范围和路径长度相关，这个数值如果较大的话，就会让时间、空间复杂度容易超出范围，且距离不容易离散化，较难优化。虽然可以用其他结构（例如平衡树）来保证复杂度，但代码复杂度就会明显增加。

方法二：指针扫描数组

把树中的每个点放进一个数组 a，并把数组 a 按照节点的 d 值排序，用两个指针 l，r 分别从前、后扫描 a 数组。

那么，指针l从左向右扫描的过程中，使得 d_{a_{l}}+d_{a_{r}} \leq k 的指针r的范围是从右向左单调递减的。

用数组 cnt_{s} 维护在 l+1 与 r 之间满足 b_{a_{i}} = s 的位置 i的个数，那么当路径的一端 x 等于 a_{l}时，满足条件的另一端 y 的个数为 r-l-cnt_{b_{a_{l}}}。

显然以上两种方式虽然不同，但是点分治过程都大差不差。

1. 找到根节点 root
2. 从 root 出发进行 Dfs 求出数组 d 和 b。
3. 执行 solve(root)
4. 删除根节点 root ,并对其每颗子树进行点分治。

代码

徐老师的代码见文件，至于我的代码上文已经提供链接。

使用重心之因

开头提到过重心来优化时间，这里详细阐述一下将重心作为根节点进行优化的原因。整个时间复杂度为 O_{(T·Nlog(N))}，其中 T是树的层数。如果遇到最坏情况（一条链，且每次选择端点为根），那么时间最差就是 O_{( N^{2}log(N))}。为了避免这种情况，我们每次分治需要选择树的重心作为根，可以让分治只递归 O_{(logN)}层，从而时间复杂度稳定在 O_{(Nlog^{2}(N))}。

例题2：P3806 【模板】点分治1

题目大意：

给定一棵有 n 个点的树，询问树上距离为 k 的点对是否存在。

存在输出 AYE，否则输出 NAY。

解析：

与上一题相似，但是本题要求的是判断是否存在距离为 k 的点，所以在指针扫描数组过程中有些许不同，但大体没有区别。条件从小于等于变为一定要等于且不在一颗子树上，同时只要找到符合条件的就可以不继续计算下去。

代码：这里

练习

习题：AcWing264、AcWing3014

洛谷题号：P4149、P5563、P2993

讲解+代码下载链接:这里