世界的尽头

树的重心

给定一棵包含 $n$ 个节点的无根树。删除某个节点以及所有与它相连的边后，原树会被分成若干个连通块。

如果删除节点 $u$ 后，剩余的最大连通块包含的节点数最小，那么节点 $u$ 就是这棵树的重心。设删除 $u$ 后得到的最大连通块大小为 $f(u)$ ，则需要求：

\min_{1 \le u \le n} f(u).

一棵树可能有一个重心，也可能有两个重心。本题只要求输出删除重心后最大连通块的节点数，不需要输出重心编号。

邻接表存树

树是一张包含 $n$ 个节点、 $n-1$ 条边的无向连通图。无向边 $(a,b)$ 需要保存为两个方向：

add(a, b);
add(b, a);

使用数组模拟邻接表：

const int N = 100010;
const int M = 2 * N;
 
int h[N];   // h[u]：节点 u 的第一条边
int e[M];   // e[i]：第 i 条边指向的节点
int ne[M];  // ne[i]：同一起点的下一条边
int idx;

其中 h[u] == -1 表示节点 u 当前没有邻边，因此建图前需要把 h 数组初始化为 -1。

加入一条从 a 指向 b 的边：

void add(int a, int b) {
  e[idx] = b;
  ne[idx] = h[a];
  h[a] = idx++;
}

新边会插入节点 a 的邻接链表表头。每次操作只修改常数个数组元素，时间复杂度为 $O(1)$ 。

DFS 统计子树大小

任取一个节点作为根，例如节点 1。执行 DFS 时，令：

\operatorname{size}(u)

表示以 u 为根的子树节点数。

对于节点 u，递归访问每个尚未访问的相邻节点 v。递归返回的 size(v) 就是删除 u 后，节点 v 所在连通块的大小。

int sum = 0;
 
for (int i = h[u]; i != -1; i = ne[i]) {
  int v = e[i];
 
  if (visited[v]) {
    continue;
  }
 
  int child_size = dfs(v);
  sum += child_size;
}

所有子树之外，还存在节点 u 上方的连通块。u 的各棵子树一共包含 sum 个节点，再排除 u 自身，上方连通块大小为：

n-\operatorname{sum}-1.

因此，删除 u 后最大连通块的大小为：

f(u)= \max\left( \max_{v\text{ 是 }u\text{ 的子节点}}\operatorname{size}(v), n-\operatorname{size}(u) \right).

DFS 返回当前子树大小：

\operatorname{size}(u) = 1+\sum_{v\text{ 是 }u\text{ 的子节点}}\operatorname{size}(v).

DFS 模板

int dfs(int u) {
  visited[u] = true;
 
  int max_part = 0;
  int subtree_sum = 0;
 
  for (int i = h[u]; i != -1; i = ne[i]) {
    int v = e[i];
 
    if (visited[v]) {
      continue;
    }
 
    int child_size = dfs(v);
    max_part = max(max_part, child_size);
    subtree_sum += child_size;
  }
 
  max_part = max(max_part, n - subtree_sum - 1);
  answer = min(answer, max_part);
 
  return subtree_sum + 1;
}

这里有两个容易混淆的变量：

subtree_sum：节点 u 的所有子树节点数之和；
max_part：删除节点 u 后，所有连通块中的最大节点数。

正确性说明

任取节点 u。将树以 DFS 起点为根后，删除 u 会得到两类连通块：

对于 u 的每个子节点 v，以 v 为根的整棵子树形成一个连通块，其大小为 dfs(v)；
除 u 及其所有子树外的节点形成上方连通块，其大小为 $n-\operatorname{size}(u)$ ，也就是 n - subtree_sum - 1。

树中任意节点删除后产生的连通块必然属于这两类，不会遗漏。算法取这些连通块大小的最大值，因此计算出的 max_part 恰好等于 $f(u)$ 。

DFS 会访问树中的每个节点，并对每个节点都计算一次 $f(u)$ 。不断使用：

answer = min(answer, max_part);

即可得到所有 $f(u)$ 中的最小值，也就是删除重心后最大连通块的节点数。因此算法正确。

AcWing 846：树的重心

题意

给定一棵包含 $n$ 个节点的树，节点编号为 $1$ 到 $n$ 。删除树中的一个节点及其相邻边后，求剩余各个连通块中节点数最大值的最小可能结果。

数据范围：

1 \le n \le 10^5.

思路

使用邻接表存储无向树，从任意节点开始 DFS。对于每个节点：

递归计算所有子树大小；
用子树大小更新最大连通块；
计算父节点方向的连通块大小；
更新全局最小答案；
返回当前子树大小。

由于无向边会同时存储两个方向，DFS 必须使用 visited 数组避免沿父边返回，造成无限递归。

完整代码

#include <algorithm>
#include <cstring>
#include <iostream>
 
using namespace std;
 
const int N = 100010;
const int M = 2 * N;
 
int h[N], e[M], ne[M], idx;
int n, answer;
bool visited[N];
 
void add(int a, int b) {
  e[idx] = b;
  ne[idx] = h[a];
  h[a] = idx++;
}
 
int dfs(int u) {
  visited[u] = true;
 
  int max_part = 0;
  int subtree_sum = 0;
 
  for (int i = h[u]; i != -1; i = ne[i]) {
    int v = e[i];
 
    if (visited[v]) {
      continue;
    }
 
    int child_size = dfs(v);
    max_part = max(max_part, child_size);
    subtree_sum += child_size;
  }
 
  // 删除 u 后，父节点方向连通块的大小
  max_part = max(max_part, n - subtree_sum - 1);
  answer = min(answer, max_part);
 
  // 返回以 u 为根的子树大小
  return subtree_sum + 1;
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  cin >> n;
 
  memset(h, -1, sizeof h);
 
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    add(a, b);
    add(b, a);
  }
 
  answer = n;
  dfs(1);
 
  cout << answer << '\n';
 
  return 0;
}

样例

输入：

输出：

删除节点 1 后，剩余连通块大小分别为 3、4 和 1，最大连通块包含 4 个节点。不存在其他节点能让最大连通块小于 4，因此答案为 4。

复杂度分析

邻接表中每条无向边存储两次。DFS 中每个节点只访问一次，每个有向边记录也只检查一次，因此：

时间复杂度为 $O(n)$ ；
邻接表、访问数组与递归栈的空间复杂度为 $O(n)$ 。

常见错误

无向边只添加一次：树的边需要同时执行 add(a, b) 和 add(b, a)。
忘记初始化 h：邻接表的结束标记是 -1，建图前必须执行 memset(h, -1, sizeof h)。
没有避免返回父节点：无向图中每条边存储两个方向，不使用 visited 或父节点参数会导致无限递归。
遗漏父节点方向的连通块：只统计各棵子树不完整，还必须计算 n - subtree_sum - 1。
把子树节点数之和当作最大连通块：应使用 max_part 记录所有连通块大小的最大值。
数组大小混淆：h 和 visited 按节点数开 N，e 和 ne 按双向边记录数开 2 * N。
答案初始化太小：应将 answer 初始化为 n 或其他足够大的值，再不断取最小值。
递归深度过大：当树退化成长度接近 $10^5$ 的链时，递归层数也可能接近 $10^5$ 。普通竞赛环境通常可以通过，但栈空间受限时需要改成迭代 DFS 或调整栈限制。

2-树的重心