专栏文章

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

HHim_shu
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipnid0o
此快照首次捕获于
2025/12/03 14:53
3 个月前
此快照最后确认于
2025/12/03 14:53
3 个月前
查看原文

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

想象你有一棵大树，树上有许多节点，节点之间用树枝连接。现在你要统计所有长度不超过K的路径（路径的长度是树枝的总权重）。直接暴力枚举所有路径会超时，怎么办？
点分治的核心思想：
  1. 找重心：找到树的“中心点”（重心），把它作为分割点。
  2. 处理当前中心：计算所有经过这个中心的路径。
  3. 拆分子树：删除中心，将树拆成几个小树，对每个小树重复上述过程。
为什么找重心？
  • 重心能保证每次分割后，子树的大小最多是原来的一半，避免递归层数过深。
  • 例如，如果树是一条链，每次选中间节点作为重心，递归层数就是 O(logn)O(log n)。

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

重心：删除该节点后，剩下的最大子树的大小最小。
如何找重心？
  1. 计算每个节点的子树大小（包括所有子孙）。
  2. 对每个节点，检查它的所有子树大小是否都不超过总节点数的一半。
示例：
假设树有5个节点，结构如下：
CPP
1
├─2
│ ├─4
│ └─5
└─3
  • 节点 11 的子树大小是 55（整个树）。
  • 删除节点 11 后，最大子树是节点 22 的子树（大小 33）。
  • 节点 22 的子树大小是 33，删除节点 22 后，最大子树是节点 11 的剩余部分（大小 22）。
    此时，节点 11 和节点 22 都可能成为重心，具体取决于实现。

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

步骤1：找到当前树的重心
  • 通过 DFSDFS 遍历，计算每个节点的子树大小，并找到重心。
步骤2：处理经过重心的路径
  • 收集所有子节点到重心的距离。
  • 统计这些距离中，两两之和 ≤K\le K 的对数。
  • 去重：减去同一子树内的路径（因为这些路径会被递归处理）。
步骤3：递归处理子树
  • 删除当前重心，将树拆分成若干子树，对每个子树重复步骤 1−31-3。

四、C++代码逐行解析

1. 数据结构定义
CPP
#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. 寻找重心函数
CPP
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. 收集距离函数
CPP
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. 统计有效路径对数（双指针法）
CPP
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. 点分治核心函数
CPP
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. 主函数
CPP
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;
}

五、示例演示

假设输入树如下（边权已标注）：
CPP
5 3  // 5个节点，K=3
1 2 1
1 3 2
2 4 1
2 5 1
树的结构：
CPP
    1
   / \
 1(2) 2(3)
 / \
1(4) 1(5)
执行过程：
  1. 第一次调用 decompose(1)decompose(1)，找到重心（假设是节点 22）。
  2. 处理节点 22：
    • 收集子树距离：节点 44 到 22 的距离是 11，节点 55 到 22 是 11，节点 11 到 22 是 11，节点 33 到 22 是 1+2=31+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（具体计算需详细模拟）。
  3. 递归处理子树：节点4、5、1、3。

六、常见问题

  1. 为什么要去重同一子树内的路径？
    • 因为这些路径实际上不经过当前重心，会在递归处理该子树时被计算。如果不去重，会重复统计。
  2. 如何选择初始节点？
    • 可以是任意节点，一般选择节点1。sz数组会在第一次调用getCentroid时自动计算。
  3. 时间复杂度如何保证？
    • 每次递归树的大小至少减半，总层数 O(logn)O(log n)，每层处理 O(nlogn)O(n log n) 时间，总时间 O(nlog2n)O(n log² n)。
通过这个教程，你应该能理解点分治的基本原理和实现细节。建议结合题目（如 POJ1741POJ 1741）进行练习，加深理解。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...