树的重心与同构：算法竞赛中的核心概念与应用

1. 树的重心与同构：算法竞赛中的核心概念

树结构在算法竞赛中占据着举足轻重的地位，而树的重心和同构判定更是各类图论问题的解题关键。去年寒假带队集训时，我发现许多选手在面对树形DP和网络流建模时，往往因为对这两个概念理解不透彻而错失解题良机。本文将结合ACM/ICPC和OI真题，拆解这两个知识点的应用场景和实战技巧。

提示：本文所有代码示例均基于C++17标准，适用于Codeforces、AtCoder等主流竞赛平台。

1.1 树的重心：定义与性质

树的重心（Centroid）是指树中满足"删除该节点后，剩余最大连通分量节点数最小"的节点。这个看似简单的定义背后隐藏着三个重要特性：

1. 存在性：每棵树至少有一个重心，最多两个重心且相邻
2. 平衡性：重心删除后产生的子树大小不超过⌊n/2⌋
3. 递归性：所有子树大小均满足|V|/2条件

cpp复制// 寻找单个重心的DFS实现
int centroid = -1;
function<void(int, int)> dfs = [&](int u, int fa) {
    size[u] = 1;
    int max_part = 0;
    for (int v : tree[u]) {
        if (v != fa) {
            dfs(v, u);
            size[u] += size[v];
            max_part = max(max_part, size[v]);
        }
    }
    max_part = max(max_part, n - size[u]);
    if (max_part <= n / 2) centroid = u;
};

在实际比赛中，重心的价值主要体现在：

• 优化树形DP时间复杂度（从O(n²)降至O(nlogn)）
• 作为分治策略的划分点（如点分治算法）
• 构建平衡树结构（如动态树维护）

1.2 重心的实战应用场景

2022年ICPC亚洲区域赛有一道典型题目：给定一棵树，要求找到所有满足"删除任意一条边后，两个新树的重心距离之和最小"的边。解题的关键在于：

1. 预处理所有节点的子树大小
2. 动态