深入理解C++树重心算法（小白也能学会的树形DP求重心教程）

为什么需要找树的重心？

在处理树上问题时，选择重心作为根节点可以有效平衡子树规模，从而优化递归或分治算法的时间复杂度。例如，在C++图论算法中的点分治（Centroid Decomposition）就依赖于树重心。

如何求树的重心？

我们通常使用树形DP求重心的方法，通过一次深度优先搜索（DFS）完成：

1. 先计算每个节点的子树大小（包括自己）；
2. 对于每个节点，找出删除它后最大连通块的大小；
3. 选择使最大连通块最小的节点作为重心。

C++代码实现

下面是一个完整的C++实现，包含详细注释：

#include <iostream>#include <vector>#include <algorithm>#include <climits>using namespace std;const int MAXN = 100010;vector<int> graph[MAXN];int subtreeSize[MAXN]; // 子树大小bool visited[MAXN];int n; // 节点总数int centroid = -1; // 重心int minMaxSubtree = INT_MAX; // 最小的最大子树大小// DFS 计算子树大小，并寻找重心void dfs(int u, int parent) {    subtreeSize[u] = 1; // 自身算一个节点    int maxSubtree = 0; // 删除u后，最大连通块的大小    for (int v : graph[u]) {        if (v == parent) continue;        dfs(v, u);        subtreeSize[u] += subtreeSize[v];        maxSubtree = max(maxSubtree, subtreeSize[v]);    }    // 还要考虑父节点方向的连通块    maxSubtree = max(maxSubtree, n - subtreeSize[u]);    // 如果当前节点产生的最大连通块更小，则更新重心    if (maxSubtree < minMaxSubtree) {        minMaxSubtree = maxSubtree;        centroid = u;    }}int main() {    cin >> n;    for (int i = 0; i < n - 1; i++) {        int u, v;        cin >> u >> v;        graph[u].push_back(v);        graph[v].push_back(u);    }    dfs(1, -1); // 假设树以1为根    cout << "树的重心是: " << centroid << endl;    cout << "删除重心后最大连通块大小: " << minMaxSubtree << endl;    return 0;}

代码说明

• subtreeSize[u]：记录以u为根的子树包含的节点数；
• maxSubtree：记录删除u后，所有连通块中最大的那个的大小；
• 特别注意：除了子树，还要考虑“上方”连通块（即 n - subtreeSize[u]）；
• 通过比较所有节点的 maxSubtree，找到最小值对应的节点即为重心。

总结

通过本教程，你已经掌握了C++树重心算法的核心思想和实现方法。无论是应对算法竞赛还是解决实际工程问题，树的重心求解都是一个强大而实用的工具。记住，关键在于理解“最大连通块最小化”这一目标，并通过一次DFS高效完成。

继续练习更多C++图论算法，你会发现树形DP求重心只是冰山一角。加油！