树分治

参考资料

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

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

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