树的重心（Centroid of a Tree）问题

1. 问题描述

树的重心是树中的一个结点，满足将它从树中删除后，剩下的各个连通块（即各个子树）的结点数的最大值最小。
一棵树可能有一个或两个重心。

• 如果一个结点是重心，那么删除它后，所有连通块的大小不超过 \(\lfloor n/2 \rfloor\)（其中 \(n\) 是树的结点总数）。
• 树的重心常用于树的分治算法（如点分治）中，因为它能保证分治的递归层数为 \(O(\log n)\)。

输入：一棵有 \(n\) 个结点的树（无向、连通、无环），通常以邻接表形式给出。
输出：找出树的所有重心。

2. 基本概念与性质

1. 连通块大小：删除一个结点 \(u\) 后，原树会被分成若干连通块，其中每个连通块是 \(u\) 的一个子树，或者是以 \(u\) 的父结点为根的子树（即树去掉以 \(u\) 为根的子树剩下的部分）。
2. 重心的定义：设 \(\text{max\_part}(u)\) 表示删除 \(u\) 后最大连通块的结点数。重心是使 \(\text{max\_part}(u)\) 最小的结点。
3. 重要性质：
   • 任意树至少有一个重心，最多有两个重心。
   • 如果有两个重心，它们必是树的一条边连接的两个结点，且树的结点数为偶数。
   • 重心可以在 \(O(n)\) 时间内用一次 DFS 求出。

3. 解法思路（一次 DFS 计算）

我们用 DFS 遍历树，在递归返回时，计算每个结点 “以它为根的子树大小” 以及 “删除它后最大连通块的大小”。

步骤：

1. 任选一个根结点（例如结点 1），DFS 遍历整棵树。
2. 对结点 \(u\)：
   • 计算 \(\text{subtree\_size}[u] = 1 + \sum_{v \in \text{children of } u} \text{subtree\_size}[v]\)。
   • 删除 \(u\) 后，连通块包括：
     a) \(u\) 的每个子树，大小分别为 \(\text{subtree\_size}[v]\)。
     b) 树中“除了以 \(u\) 为根的子树之外的部分”，其大小为 \(n - \text{subtree\_size}[u]\)。
   • 所以 \(\text{max\_part}(u) = \max\left( n - \text{subtree\_size}[u],\ \max_{v \in \text{children of } u} \text{subtree\_size}[v] \right)\)。
3. 遍历所有结点，找出使 \(\text{max\_part}(u)\) 最小的结点，即为重心。

4. 详细过程（举例）

假设树如下（6 个结点，边为 1-2, 2-3, 2-4, 1-5, 5-6）：

      1
    /   \
   2     5
  / \     \
 3   4     6

以结点 1 为根 DFS：

1. 计算子树大小：

   • 叶子 3：size=1
   • 叶子 4：size=1
   • 结点 2：size = 1 + size(3) + size(4) = 3
   • 叶子 6：size=1
   • 结点 5：size = 1 + size(6) = 2
   • 结点 1：size = 1 + size(2) + size(5) = 6

2. 对每个结点计算 \(\text{max\_part}\)：

   • 结点 1：max( n-size(1)=0, max(size(2)=3, size(5)=2) ) = max(0, 3) = 3
   • 结点 2：max( n-size(2)=3, max(size(3)=1, size(4)=1) ) = max(3, 1) = 3
   • 结点 3：max( n-size(3)=5, max(无子树) ) = 5
   • 结点 4：max(5, ...) = 5
   • 结点 5：max( n-size(5)=4, max(size(6)=1) ) = max(4, 1) = 4
   • 结点 6：max(5, ...) = 5

3. 最小 \(\text{max\_part}\) 是 3，对应结点 1 和结点 2。

4. 检查是否 ≤ \(\lfloor n/2 \rfloor = 3\)：结点1的max_part=3 ≤3，结点2=3 ≤3。

5. 重心是结点 1 和结点 2（两个重心，此时 n=6 为偶数）。

5. 算法实现（伪代码）

vector<int> tree[MAXN];
int subtree_size[MAXN];
int max_part[MAXN];
int n;
vector<int> centroids;

void dfs(int u, int parent) {
    subtree_size[u] = 1;
    max_part[u] = 0;
    for (int v : tree[u]) {
        if (v == parent) continue;
        dfs(v, u);
        subtree_size[u] += subtree_size[v];
        max_part[u] = max(max_part[u], subtree_size[v]);
    }
    // 考虑父结点方向的连通块
    max_part[u] = max(max_part[u], n - subtree_size[u]);
}

void find_centroids() {
    dfs(1, -1);
    int min_max_part = *min_element(max_part + 1, max_part + n + 1);
    for (int i = 1; i <= n; i++) {
        if (max_part[i] == min_max_part) centroids.push_back(i);
    }
}

时间复杂度：\(O(n)\)，因为只做一次 DFS。
空间复杂度：\(O(n)\) 用于存储树和递归栈。

6. 应用

• 点分治：每次选取重心作为分治点，保证递归深度 \(O(\log n)\)。
• 树的重新 rooting 时的平衡性优化。
• 某些树 DP 问题中，以重心为根可简化计算。