树的重心（最小的 子树的最大节点）（bfs，邻接表）（acwing）

#include<bits/stdc++.h>
using namespace std;
const int N=10050;
int n;
int he[N],e[N],ne[N],idx=0;    //类似链表 只不过head有多个（类似哈希）
bool st[N];
int ans=N;
void add(int a,int b)          //和链表一样的操作
{
    e[idx]=b;                //注意e[]存子树结点（下面判断易错）
    ne[idx]=he[a];
    he[a]=idx++;
}
int dfs(int k)
{
    st[k]=true;                    //访问过后 标记
    int sum=1,res=0;                 //sum存该树的节点个数，包括该节点，从一开始    res存子树的节点个数
    for(int i=he[k];i!=-1;i=ne[i])
    {
        if(st[e[i]]==false)
        {
            int s=dfs(e[i]);           //s为子树的节点个数
            sum+=s;                  //子树节点也为该树的一部分，所以要加起来
            res=max(res,s);            //res 为最大子树节点个数
        }
    }
    res=max(res,n-sum);                 //res此时为最大联通快节点个数 n-sum为断开该节点后 上面无法搜索到的部分
    ans=min(res,ans);                 //ans为最小的 最大联通快个数
    return sum;                   //返回树的节点数
}
int main(void)
{
    memset(he,-1,sizeof he);
    cin>>n;
    int m=n;
    m--;
    idx=0;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);            //双向表 所以要add双方
        add(b,a);
    }
    dfs(n);
    cout<<ans;
    return 0;
}