【题目来源】
AcWing：846. 树的重心 - AcWing题库
【题目描述】
给定一颗树，树中包含\(n\)个结点（编号\(1\sim n\)）和\(n-1\)条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
【输入】
第一行包含整数\(n\)，表示树的结点数。
接下来\(n-1\)行，每行包含两个整数\(a\)和\(b\)，表示点\(a\)和点\(b\) 之间存在一条边。
【输出】
输出一个整数\(m\)，表示将重心删除后，剩余各个连通块中点数的最大值。
【输入样例】
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
【输出样例】
4
【解题思路】
【算法标签】
《AcWing 846 树的重心》 #DFS# #树形DP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100010, M = N * 2; // 定义常量
int h[N], e[M], ne[M], idx; // 邻接表存储图
bool st[N]; // 标记数组，记录节点是否被访问过
int n, m; // n 是节点数量，m 是边的数量
int ans; // 存储最终结果，即树的重心的最小最大子树大小// 添加边的函数
void add(int a, int x) {e[idx] = x; // 存储边的终点ne[idx] = h[a]; // 将新边插入到节点 a 的邻接表头部h[a] = idx++; // 更新节点 a 的邻接表头指针
}// DFS 函数，计算以 u 为根的子树大小，并更新树的重心
int dfs(int u) {int sum = 1; // 当前子树的大小，初始为 1（包括当前节点）int uson = 0; // 当前节点的最大子树大小st[u] = true; // 标记当前节点为已访问// 遍历当前节点的所有邻接节点for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i]; // 邻接节点 jif (!st[j]) { // 如果节点 j 未被访问过int s = dfs(j); // 递归计算以 j 为根的子树大小sum += s; // 累加子树大小uson = max(uson, s); // 更新最大子树大小}}// 计算当前节点的最大子树大小（包括父节点方向的子树）int maxt = max(n - sum, uson);// 更新全局最小值ans = min(ans, maxt);return sum; // 返回以 u 为根的子树大小
}int main() {memset(h, -1, sizeof(h)); // 初始化邻接表头指针为 -1cin >> n; // 读取节点数量ans = n; // 初始化结果为最大值// 读取边的信息并构建图for (int i = 1; i <= n - 1; i++) {int a, b;cin >> a >> b; // 读取边的两个端点add(a, b); // 添加边 a -> badd(b, a); // 添加边 b -> a}dfs(1); // 从节点 1 开始 DFScout << ans; // 输出结果return 0;
}
【运行结果】
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
4