点分治是一种按节点对树分治处理的思想,常用于对满足特定条件的树上路径计数(或求最值)的问题。
其基本流程可概括为:
- 找到当前树的一个重心 $a$
- 对满足特定条件的,且 经过重心 $a$ 的 树上路径进行计数
- 删除重心 $a$,使树变成若干颗树的森林。对于其中每棵树,递归对其中的路径进行计数。(不经过重心 $a$ 的树上路径)
由于树的重心的性质,删去重心后,得到的每棵树的大小均不超过原树大小的一半,这保证了分治深度不会超过 $O(\log n)$。
若每次进行流程中第 $2$ 步操作的时间复杂都为 $O(m)$,$m$ 是当前树的大小,则点分治的总时间复杂度为 $O(n\log n)$。这是保证时间复杂度正确的关键。
例1
给定一颗 $n$ 个点的树,边有边权。
给定 $k$,询问:树上所有包含点数为 $k$ 的路径中,最大的路径长度(边权之和),以及路径长度最大时的路径数量。
限制:
- $n, k \leqslant 10^5$
分析:
这是一个对树上满足特定条件的路径的特定属性的最大化问题,考虑点分治。
考虑当前的重心 $a$。在求出这一重心后,我们需要解决的问题是:
树上所有包含点数为 $k$,且经过重心 $a$ 的路径中,最大的路径长度(边权之和),以及路径长度最大的路径数量。
形如此类的问题在点分治中非常常见。要解决这种问题,需要充分利用要统计的路径全部经过点 $a$ 这一性质。
在点分治求解过程中,对于每个重心,处理出该子树中所有节点到重心的树链,然后枚举每条树链,比如某条树链节点数为 $x$,长度为 $b$,则找之前遍历过的树链中节点数为 $k-x$ 的长度最长的树链,将这两条树链拼起来可以得到节点数为 $k$ 的树链,用其更新答案。最好一个一个分支分别处理,可以避免考虑同一个分支来的两条树链。这样枚举并且更新信息,还要存方案数。
待补