$\quad {学到了①邻接表}$
②树🌲上找连通块。记录子树的大小 sum+=s

#include<iostream>
#include<algorithm>
#include<cstring>
// 问题：如何求把点去掉以后连通块的点数的最大值---
// 解： 树的深度优先遍历DFS
// dfs 可以求出每个子树中点的数量

// 思路 例子：4结点size 假如4个点
// 那么惊奇发现，另外一边的连通块点数为 总数- 4 = n - 4
using namespace std;

const int N = 100010, M = N*2 ; //双向(正反)有向图

int n, m;

int h[N], e[M], ne[M], i;
bool st[N]; //布尔数组存当前i是否被搜过

int ans = N; //最小的最大值

//标准边加入图的模板
// 邻接表
void add(int a, int b) // 适用a->b
{
    e[i] = b; // e[]里存节点的值
    ne[i] = h[a]; // ne[]里存下一个数，即当前数next指针指向哪。以下标来存。
    h[a] = i ++; //头结点也是以下标来存。
}

// 以u为根的子树的点的【数量】
int dfs(int u) //u表示当前dfs搜到的点
{
    st[u] = true; //标记已经被搜过

    int sum = 1, res = 0; //sum存每个点当前子树大小, 从一个点开始=1 
    //res存把这个点删掉后，每一个连通块点数的最大值

    //遍历u的所有出边
    for (int y = h[u]; y != -1; y = ne[y]) //每次走到next指针(下个点)
    {
        int j = e[y]; //当前结点在图里对应的值~~编号~~(不是编号)
        if (!st[j]) 
        {
            int s = dfs(j); //如果没有搜过，一直搜。(这也就搜到树的底了) // s表示 当前子树大小
            res = max(res, s);
            sum += s; //s是当前这个点的子树（儿子），所以size加上
        }
    }

    res = max(res, n - sum); //子树和另外一边(上面)连通块点数取最大值
    ans = min(res, ans); //题意[输出]选所有最大值里最小的
    return sum;
}


int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int y = 0; y < n - 1; y++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }


    dfs(1); //从第1个点开始搜
    cout << ans << endl;
    return 0;
}