题目链接–树的重心

dfs函数解析

int dfs(int x)
{
	vis[x] = true;
	int sum = 1, cnt = 0;
	for (int i = h[x]; i != -1; i = ne[i])
		if (!vis[e[i]]) {
			int s = dfs(e[i]);//s求得的是以e[i]为根的一条分支上节点的个数（不包括e[i])
			cnt = max(cnt, s);//cnt存的是将连接e[i]的点断开后每条分支上节点个数的最大值
			sum += s;//每得一分支得节点数都会加到sum上，包括当前节点e[i]
		}
	cnt = max(n - sum, cnt);
	siz = min(siz, cnt);
	return sum;
}

关于dfs这个函数举个栗子应该就能明白了：
比如dfs(1):开始是从节点1开始的，接着到节点4，探测完4的分支节点再比较n-sum（sum包括4节点）和cnt得到的就是去除4节点后的最大连通集的节点，在探测4节点过程中会到节点3和6，也能分别求出去掉3和6后的最大连通集的节点,所以虽然dfs是从节点1开始出发的，但依靠cnt=max(n-sum,cnt)和siz=min(siz,cnt)就把去掉每个节点后的最大连通集节点数求出来了。
那这里有个问题，为什么要cnt和n-sum比较，遍历完4的两个分支3和6在网上遍历4的最后一个分支1不就好了，但问题是，4就是从1来的，已经标记1节点访问过，所以没法再往上遍历，从1出发遍历的节点只能是1的三个分支的节点数。
1的分支有2 4 7，4已经遍历过了，也得到4（包括4）的根节点数，所以只要遍历2，7就行，在从1开始时sum就为1，那sum+=s,得到的就是整个树的节点数，相当于一个节点不删除，这个不影响，因为要求的时最大集合的最小值
因为每次到一个新的节点b都是从一个相连节点a来的（a是被删的节点），而a又是从一个节点c来的，所以求a邻接的分支的最大联通集合不包括来到a的c所代表的分支，所以需要再次比较，siz=max(siz,n-sum);

完整代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 5;
int e[2 * N], ne[2 * N], h[N], idx;
bool vis[N];
int siz = N;
int n;
void add(int x, int y)
{
	e[idx] = y;
	ne[idx] = h[x];
	h[x] = idx++;
}
int dfs(int x)//这一块的工作原理逐步调试就明白了
{
	vis[x] = true;
	int sum = 1, cnt = 0;
	for (int i = h[x]; i != -1; i = ne[i])
		if (!vis[e[i]]) {
			int s = dfs(e[i]);//s求得的是以e[i]为根的一条分支上节点的个数（不包括e[i])
			cnt = max(cnt, s);//cnt存的是将连接e[i]的点断开后每条分支上节点个数的最大值
			sum += s;//每得一分支得节点数都会加到sum上，包括当前节点e[i]
		}
	cnt = max(n - sum, cnt);
	siz = min(siz, cnt);
	return sum;
}
int main()
{
	int x, y;
	cin >> n;
	memset(h, -1, sizeof h);
	for (int i = 1; i < n; i++)
	{
		cin >> x >> y;
		add(x, y); add(y, x);
	}
	dfs(1);
	cout << siz;
	return 0;
}

芜湖
一道题看了好久，我好菜wuwuwu