C++

$\color{#cc33ff}{— > 算法基础课题解}$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2;

int n;
int h[N], e[M], ne[M], idx;
//h:n个链表的链表头，e:存储每一个节点的值是多少，ne:每一个结点的next指针
bool st[N]; // 哪个点已经被遍历过了

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

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

//以u为根的子树中点的数量
int dfs(int u) { // u 表示当前已经dfs到了这个点
    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); // 当前子树的大小
            res = max (res, s);
            sum += s;
        }
    }
    res = max(res, 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(1);

    cout << ans ;
    return 0;
}