点分治(Centroid Decomposition)

点分治(Centroid Decomposition)是一种在树上进行分治的经典算法,专门用于高效统计满足特定条件的路径。它通过反复选取树的重心作为分治中心,将复杂的全树路径问题分解为若干规模减半的子问题。

概述

树上路径统计问题的核心难点在于路径数量为平方级,无法逐一枚举。点分治的思路是:任意一条路径要么经过当前分治中心,要么完全落在删除中心后的某个子树内。于是只需高效统计经过中心的路径,其余路径交给递归处理即可。由于每次以重心为中心,递归深度被限制在对数级。

核心原理

• 求重心:重心是删除后使最大连通块最小的节点,能保证子树规模至多为原来的一半,从而控制递归深度为 O(log n)。
• 统计跨中心路径:以重心为根计算各节点到重心的距离等信息,通过排序、双指针或桶计数统计满足条件的路径对。
• 容斥去重:同一子树内两点的路径会被误统计为经过中心,需要对每个子树单独再计算一次并减去。
• 递归分治:删除重心后对每个连通块重复上述过程。

每层分治处理所有节点的总代价为线性或线性对数,乘以对数级的递归层数,总复杂度通常为 O(n log n) 或 O(n log^2 n)。

应用场景

点分治常用于求解树上距离等于某定值的点对数量、距离不超过某值的点对数量、路径权值统计等问题。其加强版点分树(动态点分治)还能支持带修改的路径询问,是竞赛树上问题的重要武器。

常见问题

问:为什么必须选重心而不是随便一个点?答:选重心能保证每个子树规模至多为一半,递归层数为对数级;若随意选点可能退化为链,层数变为线性,复杂度劣化。

问:如何避免同一子树内的路径被重复统计?答:采用容斥,先按全体节点统计,再对每个子树以其到中心距离为偏移单独统计并减去,消除不真正经过中心的路径。