给定一颗树，树中包含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
解法： 通过dfs，每次统计以某点为根的子树中点的个数的最大值，再与剩余的节点比较，得到某点所有的连通块的最大值，再在各点中找出所有的点最大值中的最小值即为答案。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
int ans = N,head[N],nxt[N*2],e[N*2],tot,n;//无向图开两倍空间
bool st[N];
void add(int u,int v) {e[tot] = v;nxt[tot] = head[u];head[u] = tot++;
}
int dfs(int u) {st[u] = true;int cnt = 0,sum = 0;for(int i=head[u];i != -1;i = nxt[i]) {int j = e[i];if(!st[j]) {int s = dfs(j);cnt = max(cnt,s);//每次统计以u为根的子树中点的个数的最大值sum += s;}}cnt = max(cnt,n - sum - 1);//与剩余的点的个数比较ans = min(ans,cnt);//比较各个最大值中的最小值return sum + 1;//返回以u为根的子树中的点的个数（加上本身）
}
int main() {cin >> n;int l,r;memset(head,-1,sizeof(head));for(int i=0;i<n;i++) {cin >> l >> r;add(l,r);add(r,l);}dfs(1);cout << ans;return 0;
}