CSP复习每日一题（四）

树的重心

给定一颗树，树中包含 $n$ 个结点（编号 $1\sim n$）和 $n-1$条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义： 重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数 $n$，表示树的结点数。

接下来 $n-1$ 行，每行包含两个整数 $a$ 和 $b$，表示点 $a$ 和点 $b$ 之间存在一条边。

输出格式

输出一个整数 $m$，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

$1\le n\le 105$

输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例

4

思路

• 基本框架： $DFS$
• 判断一个结点是否是重心的方法：

  • 假设当前按照深度优先的次序遍历到第 $k$ 个结点，我们删除这个结点之后会得到第 $k$ 个结点的若干子树（每个子树都是一个连通块）以及一个包含第 $k$ 个结点的父节点的连通块。
    

  • 对于第 $k$ 个结点的若干子树，我们可以通过递归的方式将子树的返回值设置为子树的节点数量，这样就可以非常高效地获取每个子树所对应的连通块的节点数量

  • 而对于包含第 $k$ 个结点的父节点的连通块，它的节点数量可以由如下公式计算$$F=n-sum-1$$其中 $n$ 为树的总节点数，$sum$为所有子树构成的连通块的结点总数，1代表第 $k$ 个结点

  • 而我们的目标是求出将重心删除后，剩余各个连通块中点数的最大值，因此可以设置一个全局变量保存答案，然后在 $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;
}