CSP复习每日一题（四）
树的重心
给定一颗树，树中包含 n n n 个结点（编号 1 ∼ n 1∼n 1∼n）和 n − 1 n−1 n−1条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义： 重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数 n n n，表示树的结点数。
接下来 n − 1 n−1 n−1 行，每行包含两个整数 a a a 和 b b b，表示点 a a a 和点 b b b 之间存在一条边。
输出格式
输出一个整数 m m m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
1 ≤ n ≤ 105 1≤n≤105 1≤n≤105
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例
4
思路
- 基本框架： D F S DFS DFS
- 判断一个结点是否是重心的方法：
-
假设当前按照深度优先的次序遍历到第 k k k 个结点，我们删除这个结点之后会得到第 k k k 个结点的若干子树（每个子树都是一个连通块）以及一个包含第 k k k 个结点的父节点的连通块。
-
对于第 k k k 个结点的若干子树，我们可以通过递归的方式将子树的返回值设置为子树的节点数量，这样就可以非常高效地获取每个子树所对应的连通块的节点数量
-
而对于包含第 k k k 个结点的父节点的连通块，它的节点数量可以由如下公式计算 F = n − s u m − 1 F=n-sum-1 F=n−sum−1其中 n n n 为树的总节点数， s u m sum sum为所有子树构成的连通块的结点总数，1代表第 k k k 个结点
-
而我们的目标是求出将重心删除后，剩余各个连通块中点数的最大值，因此可以设置一个全局变量保存答案，然后在 D F S DFS DFS 的过程中不断更新它，具体更新的方式见代码。
-
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//树的重心，链式前向星，DFS
const int maxn = 1e5 + 1;
int n, head[maxn], len = 0, vis[maxn], ans = 1e6 - 5;struct Node {int to, next;
}e[2 * maxn];void add_edge(int u, int v) {e[++len].to = v;e[len].next = head[u];head[u] = len;
}int dfs(int k) {int son_max = 0, sum = 0;for (int i = head[k]; i; i = e[i].next) {int v = e[i].to;if (!vis[v]) {vis[v] = 1;int v_num = dfs(v);vis[v] = 0;sum += v_num;son_max = v_num > son_max ? v_num : son_max;}}// 更新答案ans = min(ans, max(son_max, n - sum - 1));return sum + 1;
}int main() {cin >> n;for (int i = 1; i < n; i++) {int u, v; cin >> u >> v;add_edge(u, v);add_edge(v, u);}dfs(1);cout << ans;return 0;
}