点分治

What · 是什么

点分治（重心分解 / Centroid Decomposition）是树上的分治框架：每次取当前连通块的重心 rt，统计所有「经过 rt」的路径对答案的贡献，然后把 rt 删除，对其余每个连通块递归同样处理。由于重心保证每块至多 n/2，递归深度 O(log n)，每层每个节点被访问一次，总复杂度 O(n log n)（加上统计逻辑自身的代价）。「路径覆盖性质」保证任意一条树上的路径都恰好在其所在连通块第一次分解到某个重心时被统计一次，从而不重不漏。其变体点分树（centroid tree）把分治重心连成一棵 O(log n) 层的树，可在线处理带修改的路径距离类问题。

Why · 为什么

How · 实现

伪代码

decompose(u):
  tot = 计算连通块大小（用当前块 dfs，忽略已删除点）
  rt = 求重心(u, tot)
  process(rt)            # 统计所有经过 rt 的路径
  removed[rt] = True
  for v in adj[rt], not removed[v]: decompose(v)
get_siz(u,f): siz[u]=1; for v!=f and not removed[v]: siz[u]+=get_siz(v,u)
get_centroid(u,tot,f):
  for v in adj[u], v!=f and not removed[v]:
    if siz[v]*2 > tot: return get_centroid(v,tot,u)
  return u
process(rt):  # 例：距离为 K 的点对数
  tf[0]=1; 记录已改下标
  for ch in adj[rt], not removed[ch]:
    dists = []
    dfs_dist(ch, rt, 1, dists)      # 到 rt 的距离
    for d in dists: ans += tf[K-d]
    for d in dists: tf[d]+=1; 记录
  清空 tf 只回滚记录过的下标

Python 实现

import sys
from collections import deque

sys.setrecursionlimit(1 << 22)


def main():
    n = 7
    edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)]
    K = 2
    G = [[] for _ in range(n + 1)]
    for a, b in edges:
        G[a].append(b)
        G[b].append(a)

    removed = [False] * (n + 1)
    siz = [0] * (n + 1)
    tf = {0: 1}
    touched = [0]
    ans = 0

    def get_size(u, f):
        siz[u] = 1
        for v in G[u]:
            if v != f and not removed[v]:
                siz[u] += get_size(v, u)
        return siz[u]

    def get_centroid(u, tot, f):
        for v in G[u]:
            if v != f and not removed[v] and siz[v] * 2 > tot:
                return get_centroid(v, tot, u)
        return u

    def collect(u, f, d, out):
        if d > K:
            return
        out.append(d)
        for v in G[u]:
            if v != f and not removed[v]:
                collect(v, u, d + 1, out)

    def decompose(u):
        nonlocal ans
        tot = get_size(u, 0)
        rt = get_centroid(u, tot, 0)
        # 统计经过 rt 且距离恰为 K 的点对
        for ch in G[rt]:
            if removed[ch]:
                continue
            dists = []
            collect(ch, rt, 1, dists)
            for d in dists:
                ans += tf.get(K - d, 0)
            for d in dists:
                tf[d] = tf.get(d, 0) + 1
                touched.append(d)
        # 回滚本层 tf（只清改动过的下标，避免 O(n^2)）
        for d in touched:
            tf[d] = 0
        touched.clear()
        tf[0] = 1
        touched.append(0)
        removed[rt] = True
        for v in G[rt]:
            if not removed[v]:
                decompose(v)

    decompose(1)
    print("pairs with distance =", K, ":", ans)
    # 手算：距离2的点对 (1,4),(1,5),(1,6),(1,7),(2,3),(4,5),(6,7) 共 7 对
    assert ans == 7, ans
    print("OK")


if __name__ == "__main__":
    main()

易错点

• 选重心前必须重新计算当前连通块的 siz（包含向上部分），用旧全树 siz 判断会选错重心导致层数退化
• 清空 tf 用 memset 导致 O(n^2)：必须记录改动过的下标再逐个回滚
• 统计「经过重心」的路径时把同一子树内的两点直接配对（如 ch 内两点经过 rt 计数）会重复计算：需先查桶再更新，保证配对的两端来自不同子树
• removed[rt]=True 时机：在统计完所有经过 rt 的路径之后、递归子树之前
• 带边权时距离类型用 long，剪枝 d>K 要按边权判断
• 点分树中求每层 tot 用「上层 tot - 重心方向大小」，不要重跑全树 DFS

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/tree-divide/
• oiwiki_raw✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/graph/tree-divide.md
• CP-Algorithms✓ https://cp-algorithms.com/graph/centroid_decomposition.html