树上分治笔记

(不)经过自己

Posted by Ghastlcon on February 3, 2018
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 树上分治笔记

点分治

用于求出树上的某种答案。

还是给个例子吧

给定 $1$ 颗 $n\leq 10^5$ 个结点的树,树的边有边权,求满足 $u$ 到 $v$ 距离等于 $k\leq 10^9$ 的无序点对 $(u,v)$ 数。

无根转有根

随便选取树中 $1$ 个结点 $x$,将其作为根。

则点对 $(u,v)$ 有 $2$ 中可能:$u\Leftrightarrow v$ 经过点 $x$,或不经过点 $x$ 。

对于不经过点 $x$ 的情况,递归处理即可。

若经过 $x$,则扫描 $x$ 的每个子树,记录下子树中每个点到 $x$ 的距离,然后排序单调(或者启发式合并)即可。

重心

上面的做法其实存在问题:若树退化成链,而又是随便选取的 $x$,因此有可能 $x$ 为链的 $1$ 端。递归下去,有可能选取的 $x$ 再次为链的 $1$ 端……如此递归 $n$ 次,每次平均遍历了 $\frac{n}{2}$ 个结点,因此时间复杂度退化为 $O(N^2\log N)$ 。

因此,我们不能随意找 $x$,而应该找出重心(即 $x$):删除重心后,分裂成的多颗子树中大小最大的尽量小。

定理:对于任意大小为 $z$ 的树,删除它的重心后分裂出的多颗子树中大小最大的也不会超过 $\frac{z}{2}$

应用上面的定理,每次子树大小减半,因此最多递归 $\log n$ 次,每次平均遍历了 $\frac{n}{2}$ 个结点,因此时间复杂度为 $O(N\log^2N)$ 。

重心也很简单:先随便找 $1$ 点为根,算出每个结点的子树大小,再扫描 $1$ 遍即可解决。


证明上面的定理。

假设 $u$ 是树的重心,且删除之后大小最大的子树的根为 $v$,该子树的大小为 $z_v$ 。

利用反证法,假设有 $z_v>\frac{z}{2}$ 。

那么我们删除 $v$ 之后,产生的 $1$ 颗子树大小为 $z_v-1$,另 $1$ 颗为 $z-z_v$,即该子树大小 $<\frac{z}{2}$ 。

删除 $u$ 或删除 $v$,有且仅有 $2$ 颗子树的大小发生了变化。(此处请自行画图)
(其实上面这句话是废话,反而有可能把你搞懵)
(如果看不懂这句话直接跳过即可)

整理上述,得:
删除 $v$ 后,$2$ 子树大小为 $a_v=z_v-1$ 与 $b_v<\frac{z}{2}$;
删除 $u$ 后,$2$ 子树大小为 $a_u=z_v$ 与 $b_u=z-z_v-1$ 即 $b_u<\frac{z}{2}-1$ 。

由于设有 $z_v>\frac{z}{2}$,因此 $z_v-1\geq \frac{z}{2}$,得 $a_v>b_v$ 。同理得到 $a_u>b_u$ 。

此时 $b_u,b_v$ 已经对 $u,v$ 到底哪个才是真正的重心不起任何作用:$a_u>b_u,a_v>b_v$,只需要看 $a_u,a_v$ 即可决定哪个是重心

同时有 $a_v<a_u$,得 $v$ 为重心,与前面假设的 $u$ 为重心矛盾。

$\blacksquare \text{Q.E.D.}$

边分治

不同于点分治,删除 $1$ 条边之后会并且仅会产生 $2$ 颗子树。

因此随便选取 $1$ 条边之后,计算 $u\Leftrightarrow v$ 经过该边的对数变得更方便了:只有 $2$ 颗子树,连合并都不需要了。

虚点

非常遗憾,这样子的边分治是可以被卡掉的。

无论你选哪条边,按照什么顺序分治,都必须递归 $n$ 次,时间复杂度退化到 $O(N^2\log N)$ 。

既然改变选取的顺序没用了,能否在不改变答案的前提下改变树的形态?

加入虚点。请注意,做启发式合并时,不要把虚点加入到集合中,以免影响答案。

定义重边为删除该边后,产生的 $2$ 子树,大者的大小最小。

定理:对于任意大小为 $z$ 的树,若每个点的度均不超过 $d$,删除它的重边后分裂出的 $2$ 棵子树的大小均在区间 $[\frac{z}{d+1},\frac{zd}{d+1}]$ 内

如果我们严格控制该树为 $2$ 叉树,则 $d=3$,产生子树大小在 $[\frac{n}{4},\frac{3n}{4}]$ 内,最坏情况下每次子树大小变成原来的 $\frac{3}{4}$,即递归深度为 $\log_4^3 n$ 。

总时间复杂度为 $O(N\log_4^3 N\log N)$ 。


链分治