思路：先用邻接表创建出题目中所给的树，之后任取一点开始进行 dfs（位置任选是因为题目本身给的是连通无向图，故取任意点都能走到其他各个点）同时开一个bool数组避免同一节点重复计算。给定一个固定 size 的树，以任意点 u 为例，首先求以 u 为根的子树的节点总数 p，然后得出剩下非子树部分的规模size - p，两者比对求出最大值，将比对结果再与遍历历史中的 最小的 最大连通图规模比较，循环&递归结束后保留下的最小值，就是题目的解

#include<iostream>
#include<cstring>
using namespace std;const int N = 1e5 + 10, M = 2 * N;//因为是无向图所以至多存在M条边int h[N],e[M],ne[M],idx;
//与链表大致相同，h存各个无向图节点的地址，e存节点内容，ne是下个节点的下标，idx保存每个节点的地址（形式上为编号）
int n,ans = N;
//ans表示重心的所有子树中，规模最大子树的结点数
bool st[N];
//保存节点是否被访问过void add(int a, int b)
{e[idx] = b;//给节点值ne[idx] = h[a];//给next地址h[a] = idx++;//开新地址
}int dfs(int u)
{st[u] = true;int sum = 1,res = 0;//sum 表示该以该节点为根的子树的节点数，res 保存抠掉当前节点后最大连通图规模for(int i = h[u];i != -1 ;i = ne[i]){int j = e[i];if(!st[j]){int s = dfs(j);//以u节点为根的 j 这单棵子树的节点数res = max(res,s);//记录最大联通子图的节点数sum += s;//以 j 为根的子树的节点数}}res = max(res,n - sum);//n - sum 是该节点“上面”所有未遍历到的树的所有节点数ans = min(res,ans);//保存遍历历史中最小的最大连通图规模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(2);//位置任选是因为题目本身给的是连通无向图，取任意点都能走到其他各个点。cout<< ans << endl;return 0;
}