这一题在算法基础课的搜索与图论中见过，但比较难理解，在此写一篇题解，梳理梳理。

首先需要将题目的意思读懂，删除重心后各连通块的点数的最大值，而重心又是指删除该点后，各连通块中点数的最大值最小，而我们就是要寻找这个重心。

不太好理解，看一幅图就知道了。

那我们可以依次删除一个点，假设它为重心，求出连通块的点数最大值，然后再删除其它点，也求出最大值，在所有最大值中求解一个最小值就是我们的解了。

而我们就转化为在删除一个点后求剩余连通块点数的最大值。

1. 选取一个节点，不一定必须从1开始，1 - n中任选一个即可。
2. 由该节点进行深度优先遍历。
3. 在遍历的过程中，需统计每一棵子树的数量，并取其MAX，每一颗子树累加至sum。
4. 而未被遍历到的节点则为n - sum，取其MAX。
5. 上述过程对删除一个节点的连通块的点数最大值，在取一个MIN，不断更新，就是我们的解。

值得注意的是，dfs就是有这样一个特点，不撞南墙不回头，所以，先走到叶子节点不断回溯完成的，并注意标记，每个节点只能走一次，否则会出现重复统计的情况。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXNN = 1e5 + 10, MAXNM = 2 * MAXNN;
int n, ans = MAXNN;
int g[MAXNN], h[MAXNN], e[MAXNM], ne[MAXNM], idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int f(int u)
{ 
    g[u] = 1;
    int sum = 1, res = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!g[j]) {
            int s = f(j); 
            res = max(res, s);
            sum += s;
        }
    }
    res = max(res, n - sum);
    ans = min(ans, res); 
    return sum;
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof(h));
    //编号为1 - n 
    //n - 1条边 
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        //无向图，此时a->b，b->a
        add(a, b), add(b, a); 
    }

    f(1);
    cout << ans << endl;
    return 0;
}