C语言树分治算法详解（从零开始掌握点分治与树的重心分解）

为什么需要找“重心”？

树的重心是指删除该节点后，剩余各连通块中最大子树的节点数最小的点。选择重心作为分治中心，可以保证递归深度不超过 O(log n)，从而避免退化成链导致的时间复杂度爆炸。

例如，对于一棵有 n 个节点的树，其重心满足：删除它之后，任意子树的大小 ≤ n/2。

C语言实现步骤

下面我们将用 C 语言实现一个基础的点分治算法框架，用于统计树中距离等于 K 的点对数量（经典问题）。

步骤概览：

1. 建图（邻接表）
2. 找重心
3. 计算经过重心的合法路径
4. 标记重心已访问，递归处理子树

完整代码示例：

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 10005#define INF 0x3f3f3f3ftypedef struct Edge {    int to, next;} Edge;Edge edges[MAXN * 2];int head[MAXN], edge_cnt = 0;int size[MAXN], max_sub[MAXN], vis[MAXN];int n, k, root, total_size, ans;void add_edge(int u, int v) {    edges[edge_cnt].to = v;    edges[edge_cnt].next = head[u];    head[u] = edge_cnt++;}void get_size(int u, int fa) {    size[u] = 1;    max_sub[u] = 0;    for (int i = head[u]; i != -1; i = edges[i].next) {        int v = edges[i].to;        if (v == fa || vis[v]) continue;        get_size(v, u);        size[u] += size[v];        if (size[v] > max_sub[u]) max_sub[u] = size[v];    }}void get_root(int u, int fa) {    int max_part = total_size - size[u];    if (max_sub[u] > max_part) max_part = max_sub[u];    if (max_part < max_sub[root] || root == -1) root = u;    for (int i = head[u]; i != -1; i = edges[i].next) {        int v = edges[i].to;        if (v == fa || vis[v]) continue;        get_root(v, u);    }}void calc(int u, int fa, int dist, int cnt[]) {    if (dist > k) return;    ans += cnt[k - dist];    for (int i = head[u]; i != -1; i = edges[i].next) {        int v = edges[i].to;        if (v == fa || vis[v]) continue;        calc(v, u, dist + 1, cnt);    }}void dfs(int u, int fa, int dist, int cnt[], int op) {    if (dist > k) return;    cnt[dist] += op;    for (int i = head[u]; i != -1; i = edges[i].next) {        int v = edges[i].to;        if (v == fa || vis[v]) continue;        dfs(v, u, dist + 1, cnt, op);    }}void solve(int u) {    vis[u] = 1;    int cnt[k + 1];    memset(cnt, 0, sizeof(cnt));    cnt[0] = 1;    for (int i = head[u]; i != -1; i = edges[i].next) {        int v = edges[i].to;        if (vis[v]) continue;        calc(v, u, 1, cnt);        dfs(v, u, 1, cnt, 1);    }    for (int i = head[u]; i != -1; i = edges[i].next) {        int v = edges[i].to;        if (vis[v]) continue;        dfs(v, u, 1, cnt, -1); // 清除影响    }    for (int i = head[u]; i != -1; i = edges[i].next) {        int v = edges[i].to;        if (vis[v]) continue;        get_size(v, u);        total_size = size[v];        root = -1;        get_root(v, u);        solve(root);    }}int main() {    scanf("%d %d", &n, &k);    memset(head, -1, sizeof(head));    for (int i = 0; i < n - 1; i++) {        int u, v;        scanf("%d %d", &u, &v);        add_edge(u, v);        add_edge(v, u);    }    get_size(1, -1);    total_size = size[1];    root = -1;    max_sub[root] = INF;    get_root(1, -1);    solve(root);    printf("%d\n", ans);    return 0;}

关键函数说明

• get_size：计算子树大小
• get_root：寻找当前树的重心
• calc：统计经过重心的合法路径数量
• solve：主分治函数，递归处理子树

总结

分治算法教程的核心在于“分而治之”。通过合理选择重心，C语言树分治能在 O(n log n) 时间内高效解决许多树上路径问题。掌握这一技巧，不仅能提升算法能力，还能在编程竞赛中应对更复杂的图论挑战。

建议初学者先理解重心的性质，再逐步调试上述代码，结合具体样例（如 n=5, k=2 的小树）手动模拟过程，加深理解。

希望这篇关于C语言树分治、树的重心分解和点分治算法的详细教程能助你迈出算法进阶的第一步！