树的重心

题目链接：https://www.acwing.com/problem/content/847/

题目描述

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

输入描述

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

输出描述

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

示例

输入

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

输出

4

分析

本题要寻找一个满足某些条件的重心，显然我们要枚举每一个节点去判断。
我最初的想法是对每个点都进行一次如下操作：

1. 将该点从树中删除
2. 求所有连通块点数和的最大值
3. 将求出的最大值与当前记录的最大值作比较，视情况更新

该思路实现稍微有点麻烦，且需要遍历整个树n次(共n个节点)，时间复杂度较高，AC代码中给出了另一种思路，只需要遍历树一次，比较难以描述，直接参看代码及注释。

AC代码

---

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 1;
int n;
int h[N], e[2 * N], ne[2 * N];
int idx;
int ans = N;
bool st[N];

void add(int x, int y)
{
	e[idx] = y;
	ne[idx] = h[x];
	h[x] = idx;
	idx++;
}

/*函数返回值为：
* 以u为根节点的子树去除u后
* 各连通块的点数之和
* 但在求解时还进行了很多操作
* 继续看内部实现*/  
int dfs(int u)
{
	st[u] = true;
	int sum = 1, res = 0;
	for (int i = h[u]; i != -1; i = ne[i])
	{
		if (!st[e[i]])	//这一步保证下面求的是
		{				//以u下面的各连通块点数和
			int t = dfs(e[i]);
			sum += t;
			res = max(res, t);
		}
	}

	res = max(res, n - sum);	//n-sum则求出u上面连通块的点数和
	ans = min(ans, res);
	return sum;
}

int main()
{
	cin >> n;
	memset(h, -1, sizeof(h));
	for (int i = 0; i < n - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	dfs(1);		//传入根节点
	cout << ans << endl;
	return 0;
}