点分治（Centroid Decomposition）超详细C++教程

Him_shu · 2025-04-11 20:17:48 · 算法·理论

一、算法思想：把大树拆成小树

想象你有一棵大树，树上有许多节点，节点之间用树枝连接。现在你要统计所有长度不超过K的路径（路径的长度是树枝的总权重）。直接暴力枚举所有路径会超时，怎么办？

点分治的核心思想：

找重心：找到树的“中心点”（重心），把它作为分割点。
处理当前中心：计算所有经过这个中心的路径。
拆分子树：删除中心，将树拆成几个小树，对每个小树重复上述过程。

为什么找重心？

重心能保证每次分割后，子树的大小最多是原来的一半，避免递归层数过深。
例如，如果树是一条链，每次选中间节点作为重心，递归层数就是 O(log n)。

二、重心的定义与寻找方法

重心：删除该节点后，剩下的最大子树的大小最小。
如何找重心？

计算每个节点的子树大小（包括所有子孙）。
对每个节点，检查它的所有子树大小是否都不超过总节点数的一半。

示例：
假设树有5个节点，结构如下：

1
├─2
│ ├─4
│ └─5
└─3

节点 1 的子树大小是 5（整个树）。
删除节点 1 后，最大子树是节点 2 的子树（大小 3）。
节点 2 的子树大小是 3，删除节点 2 后，最大子树是节点 1 的剩余部分（大小 2）。
此时，节点 1 和节点 2 都可能成为重心，具体取决于实现。

三、算法步骤详解（以统计路径长度 \le K 为例）

步骤1：找到当前树的重心

通过 DFS 遍历，计算每个节点的子树大小，并找到重心。

步骤2：处理经过重心的路径

收集所有子节点到重心的距离。
统计这些距离中，两两之和 \le K 的对数。
去重：减去同一子树内的路径（因为这些路径会被递归处理）。

步骤3：递归处理子树

删除当前重心，将树拆分成若干子树，对每个子树重复步骤 1-3。

四、C++代码逐行解析

1. 数据结构定义

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 1e4 + 5;          // 最大节点数
vector<pair<int, int>> tree[MAXN]; // 邻接表存树：{邻接节点, 边权}
bool deleted[MAXN];                // 标记节点是否被删除（作为重心处理过）
int sz[MAXN];                      // sz[u]表示以u为根的子树大小
int k, ans;                        // 目标距离K，答案ans

2. 寻找重心函数

void getCentroid(int u, int parent, int totalNodes, int& centroid) {
    sz[u] = 1;                     // 初始化当前节点子树大小为1
    int maxSubtree = 0;            // 记录u的最大子树大小
    for (auto& [v, w] : tree[u]) { // 遍历所有邻接节点
        if (v == parent || deleted[v]) continue; // 跳过父节点和已删除节点
        getCentroid(v, u, totalNodes, centroid); // 递归计算子节点
        sz[u] += sz[v];            // 累加子树大小
        maxSubtree = max(maxSubtree, sz[v]); // 更新最大子树
    }
    // 检查剩余部分（totalNodes - sz[u]）是否更大
    maxSubtree = max(maxSubtree, totalNodes - sz[u]);
    // 如果当前节点更优，则更新重心
    if (maxSubtree < sz[centroid] || centroid == -1) {
        centroid = u;
    }
}

3. 收集距离函数

void collectDistances(int u, int parent, int currentDist, vector<int>& distances) {
    distances.push_back(currentDist); // 记录当前节点到重心的距离
    for (auto& [v, w] : tree[u]) {
        if (v == parent || deleted[v]) continue;
        collectDistances(v, u, currentDist + w, distances); // 递归收集子节点距离
    }
}

4. 统计有效路径对数（双指针法）

int countValidPairs(vector<int>& dists) {
    sort(dists.begin(), dists.end()); // 排序距离数组
    int cnt = 0, left = 0, right = dists.size() - 1;
    while (left < right) {
        if (dists[left] + dists[right] <= k) { // 满足条件
            cnt += right - left; // left和right之间的所有节点都满足
            left++;              // 移动左指针
        } else {
            right--;            // 不满足，移动右指针
        }
    }
    return cnt;
}

5. 点分治核心函数

void decompose(int u) {
    int centroid = -1;
    getCentroid(u, -1, sz[u], centroid); // 找到重心
    deleted[centroid] = true;            // 标记已处理

    vector<int> totalDists;              
    totalDists.push_back(0);             // 重心到自身的距离为0

    // 遍历所有邻接子树
    for (auto& [v, w] : tree[centroid]) {
        if (deleted[v]) continue;

        vector<int> subDists;
        collectDistances(v, centroid, w, subDists); // 收集子树距离

        // 减去同一子树内的非法路径（这些路径不经过重心）
        ans -= countValidPairs(subDists);

        // 合并到总距离列表
        totalDists.insert(totalDists.end(), subDists.begin(), subDists.end());
    }

    // 统计所有经过重心的合法路径
    ans += countValidPairs(totalDists);

    // 递归处理子树
    for (auto& [v, w] : tree[centroid]) {
        if (!deleted[v]) {
            decompose(v);
        }
    }
}

6. 主函数

int main() {
    int n;
    cin >> n >> k;

    // 建立树的邻接表
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        tree[u].emplace_back(v, w);
        tree[v].emplace_back(u, w);
    }

    // 初始化
    memset(deleted, false, sizeof(deleted));
    ans = 0;
    decompose(1); // 从节点1开始分解

    cout << ans << endl;
    return 0;
}

五、示例演示

假设输入树如下（边权已标注）：

5 3  // 5个节点，K=3
1 2 1
1 3 2
2 4 1
2 5 1

树的结构：

    1
   / \
 1(2) 2(3)
 / \
1(4) 1(5)

执行过程：

第一次调用 decompose(1)，找到重心（假设是节点 2）。
处理节点 2：
- 收集子树距离：节点 4 到 2 的距离是 1，节点 5 到 2 是 1，节点 1 到 2 是 1，节点 3 到 2 是 1+2=3。
- totalDists = [0, 1, 1, 1, 3]
- 统计满足d[i]+d[j] <=3的对数：
  - 排序后：[0,1,1,1,3]
  - 双指针计算得到：0+1,0+1,0+1,0+3 → 有效对数为10（具体计算需详细模拟）。
递归处理子树：节点4、5、1、3。

六、常见问题

为什么要去重同一子树内的路径？
- 因为这些路径实际上不经过当前重心，会在递归处理该子树时被计算。如果不去重，会重复统计。
如何选择初始节点？
- 可以是任意节点，一般选择节点1。sz数组会在第一次调用getCentroid时自动计算。
时间复杂度如何保证？
- 每次递归树的大小至少减半，总层数 O(log n)，每层处理 O(n log n) 时间，总时间 O(n log² n)。

通过这个教程，你应该能理解点分治的基本原理和实现细节。建议结合题目（如 POJ 1741）进行练习，加深理解。