深入理解C语言树重心算法（小白也能掌握的树形DP实战指南）

为什么需要找树的重心？

树的重心在很多高级算法中扮演关键角色，例如：

• 点分治（Centroid Decomposition）算法的基础
• 优化树形动态规划（树形DP入门必备技巧）
• 平衡树结构、减少递归深度

掌握树的重心求解方法，是进阶图论和算法设计的重要一步。

算法思路详解

我们采用深度优先搜索（DFS）来遍历整棵树，并在回溯过程中计算每个节点作为根时的最大子树大小。

核心思想：

1. 任选一个节点作为根（通常选0或1号节点）
2. 对每个节点u，计算其所有子树的大小
3. 同时考虑“上方”的部分（即整棵树减去以u为根的子树），这部分大小为 n - size[u]
4. 取 max(所有子树大小, n - size[u])，这就是删除u后最大连通块的大小
5. 遍历所有节点，找到使该值最小的节点，即为重心

C语言实现代码

下面是一个完整的、可运行的C语言程序，用于求解树的重心：

#include <stdio.h>#include <stdlib.h>#include <string.h>// 最大节点数#define MAXN 100010int n;int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], edge_cnt = 0;int size[MAXN]; // 子树大小int min_max_subtree = MAXN; // 最小的最大子树大小int centroid = -1; // 重心节点int visited[MAXN];// 添加无向边void add_edge(int u, int v) {    to[edge_cnt] = v;    nxt[edge_cnt] = head[u];    head[u] = edge_cnt++;}// DFS计算子树大小并寻找重心void dfs(int u, int parent) {    size[u] = 1;    int max_subtree = 0; // 当前节点u的最大子树大小    // 遍历所有邻接点    for (int i = head[u]; i != -1; i = nxt[i]) {        int v = to[i];        if (v == parent) continue;        dfs(v, u);        size[u] += size[v];        if (size[v] > max_subtree) {            max_subtree = size[v];        }    }    // 考虑“上方”部分（父方向的连通块）    int up_part = n - size[u];    if (up_part > max_subtree) {        max_subtree = up_part;    }    // 更新重心    if (max_subtree < min_max_subtree) {        min_max_subtree = max_subtree;        centroid = u;    }}int main() {    // 初始化邻接表    memset(head, -1, sizeof(head));        // 输入节点数    scanf("%d", &n);    // 输入n-1条边    for (int i = 0; i < n - 1; i++) {        int u, v;        scanf("%d %d", &u, &v);        // 假设节点编号从1开始        add_edge(u, v);        add_edge(v, u);    }    // 从节点1开始DFS    dfs(1, -1);    printf("树的重心是: %d\n", centroid);    printf(删除重心后最大连通块大小: %d\n", min_max_subtree);    return 0;}

代码说明

上述代码使用邻接表存储树结构，通过一次DFS完成重心查找。关键点包括：

• size[u]：记录以u为根的子树包含的节点总数
• max_subtree：记录删除u后，所有连通块中的最大节点数
• 特别注意要比较“上方”部分（n - size[u]）

时间复杂度分析

整个算法只需一次DFS遍历，时间复杂度为 O(n)，空间复杂度也为 O(n)，非常高效。这也是为什么图论算法C语言实现中常采用此类方法。

总结

通过本教程，你已经掌握了C语言树重心算法的核心思想与实现方式。树的重心不仅是理论概念，更是解决复杂图论问题的实用工具。建议你动手编写并调试上述代码，加深理解。当你熟练掌握这一技巧后，就可以进一步学习点分治等高级算法了！

关键词回顾：C语言树重心算法、树的重心求解、图论算法C语言实现、树形DP入门