点分治

参考资料

• 点分治 - OI Wiki

简介

点分治 用于统计树上与路径相关的信息。每次取当前连通块的 重心 为分治中心，统计所有经过重心的路径的贡献，再删去重心，对每棵子树递归处理。

取重心保证每层子块大小至多减半，递归深度 $O(\log n)$，总复杂度通常为 $O(n\log n)$ 或再带一个 $\log$。它能解决「树上距离为 $k$ 的点对是否存在」等一类问题。

例题

洛谷 P3806 【模板】点分治

给定一棵 $n$ 个点的带边权树和 $m$ 次询问，每次询问树上是否存在距离恰为 $k$ 的点对。