题目传送门
题目描述
给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，
剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数n，表示树的结点数。
接下来n-1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。
输出格式
输出一个整数m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
(1≤n≤10^5)
样例
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4
思路
树的DFS遍历
树的DFS遍历基本框架
st[u] = true;
for(int i = h[x]; i != -1; i = ne[i])
{
int v = ver[i];
if(!st[v])
{
dfs(v);
......
}
}
注意
树的dfs遍历不需要回溯（至少这道题是不用的）
其他题目本蒟蒻还不晓得
注释
本人一开始也十分不能理解y总的代码为什么就实现了题目的要求
一直看 看不懂
之后选择模拟+思考 有了点个人的理解（应该说我能理解的理解）
注释就放在代码里吧
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e5 + 10, M = N << 1; // N是点 M是边 因为无向图 需要两倍 2*(n-1)
int n, ans = N; // ans 存储题目中所求的 最大值的最小值
int idx, h[N], ver[M], ne[M]; // 邻接表存边
bool st[N]; // 判断有无遍历过
void add(int x, int y) // 邻接表添加边
{
ver[idx] = y, ne[idx] = h[x], h[x] = idx ++;
}
int dfs(int u)
{
st[u] = true; //标记已遍历
int res = 0, sum = 1;
for(int i = h[u]; i != -1; i = ne[i]) // 遍历所连接的边
{
int v = ver[i]; // 把 编号 变为 点号
if(!st[v])
{
/*
siz表示 不包括 已遍历点的 子树的点数
（不包括已遍历点 指的是 不能跨过已遍历点）
res 表示在 u （dfs中的参数u）为重心时
删去u节点后的最大连通点数
sum表示 包括u节点能遍历到的点的总数
/*
int siz = dfs(v);
res = max(res, siz);
sum += siz;
}
}
/*
（这里建议画图模拟理解）
最后对 当前能遍历到的点的res
（在 u （dfs中的参数u）为重心时
删去u节点后的最大连通点数）
与 不能遍历到的点 n-sum （要减去u这个点的）
因为我们是从 上一个点过来的， 树是连通图
所以保证了 n-sum 所表示的连通点数的点是连通的
当u为起始点时 n-sum == 0
然后 ans = 最大值的最小值
*/
res = max(res, n - sum);
ans = min(ans, res);
return sum;
}
int main()
{
memset(h, -1, sizeof h); // 初始化
scanf("%d", &n);
for(int i = 0; i < n-1; i ++) // 读边
{
int x, y;
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dfs(1);
printf("%d
", ans);
return 0;
}