分析:

在DFS遍历树的过程中，记录以每个节点为根节点的子树中含有的节点数目并返回，同时计算出删除节点u后，划分出的联通块的节点数，比较出最大节点数的最小值并记录

联通块的划分:

注意:

1.将树存储为无向图的形式，则无论从哪个节点开始遍历，都能遍历完所有节点；若想存储为有向图的形式，则必须知道树的根节点以及各边的指向，否则无法遍历到树的所有节点

2.不存在重复边的n个点组成的无向图，至多构成2*n条边

3.h[]数组要初始化为全-1，表示所有点都未构成边

代码:

#include<bits/stdc++.h>
using namespace std;

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

int n,a,b;
int ans = N;    // 记录答案 剩余各个连通块中点数的最大值的最小值

void add(int a,int b)   // 添加边a->b
{
    e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}

// dfs(u)返回以u为根的子树中点的数量
int dfs(int u)
{
    st[u] = 1;      // 标记被搜过
    int sum = 1;    // 以u为根的子树的节点数量 初始1(包含u)
    int res = 0;    // 删除节点u后 划分出的所有联通块的节点数目最大值
    for(int i = h[u];i != -1;i = ne[i])
    {
        int j = e[i];   // 由边编号找到对应边节点
        if(!st[j])
        {
            int s = dfs(j);     // 该子树的节点数目
            sum += s; 
            res = max(res,s);   // 删除u后 该子树是一个联通块
        }
    }
    res = max(res,n - sum);     // 除去以u为根的子树 剩下的部分也是一个联通块
    ans = min(res,ans);         // 更新最小值
    return sum;
}


int main()
{
    cin >> n;
    memset(h,-1,sizeof h);      // 初始化h[]数组(全-1 一开始没有添加任何边)
    for(int i = 1;i < n;i ++)
    {
        cin >> a >> b;
        add(a,b);add(b,a);  // 存储为无向图的形式 确保无论从哪个点出发 都能遍历到所有节点
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}