点分治 | Misaka's Blog

前言

做题遇到这个不会，来学一下，应该还不算晚。

和序列分治挺像的，只是搬到树上而已。

用途

常用于树上路径统计问题。

算法过程

如果学过序列分治可以更容易地理解树上点分治。与序列分治干的事情差不多：在序列分治中，我们把要统计的区间按当前分治区间 $[l,r]$ 分为三部分，被 $[l,mid)$ 包含 / 被 $(mid,r]$ 包含 / 跨过中点 $mid$ 的区间。前两类继续递归分治，只计算最后一种的贡献。由于每次区间长度减半，区间数量翻倍，故分治每层遍历的总复杂度均为 $\mathcal{O}(n)$ ，一共 $\log n$ 层，总复杂度 $\mathcal{O}(n\log n)$ 。

然而在点分治中，我们要统计的东西从区间变成了路径，每次同样可以找到一个划分点 $rt$ ，则需要被统计的路径也可以分为经过 $rt$ 的路径与不经过 $rt$ 的路径，当前只需要以 $rt$ 为根处理经过 $rt$ 的路径，处理完之后将 $rt$ 删除，在 $rt$ 的每一棵子树中找到下一个划分点，递归解决剩下的情况即可。

点分治的核心在于如何选取每层的划分点 $rt$ 。如果每次选择子树的重心作为新的划分点，由树的重心性质可得，若当前树点数为 $n$ ，若以树的重心为根，其所有子树的大小均不超过 $\frac{n}{2}$ （可以使用反证法，若有一个子树大小大于一半，那么将当前重心向那棵子树移动显然更优）。因此每次子问题数量翻倍，规模减半，故每层分治总复杂度均为 $\mathcal{O}(n)$ ，共递归 $\log n$ 层，时间复杂度也是 $\mathcal{O}(n\log n)$ 。