树分治

Summary

树分治通过分治来处理树上与路径相关的统计问题，最常用的是点分治：每次取当前连通块的重心作为分治中心，先统计所有经过重心的路径的贡献，再删去重心，把树拆成若干子树并对每棵子树递归处理。以重心为中心保证每层的子块规模至多减半，递归深度只有 O(logn) 层，加上每层的统计代价，总复杂度通常是 O(nlogn) 或再多一个 log。它擅长求解「树上是否存在距离恰为 k 的点对」以及各种按路径长度计数的问题。文末以对应的模板题作为例题，练习重心求法与经过中心的路径统计。

参考资料

• 树分治 - OI Wiki

简介

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

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

例题

洛谷 P3806 【模板】点分治

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