思路

• 剩余联通块的点数分为两个情况
  • 当前节点子节点的连通块
  • 当前节点的父节点连通块
• 采用dfs遍历当前的子节点
  • 返回的是当前节点的连通块大小
  • 当前节点的联通块的大小为当前子节点的连通块大小之和
  • 需要记录当前节点的子节点的最大连通块
  • 父节点的联通块大小为总结点数-子节点的所有连通块大小
• 剩下就是写dfs了

代码

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

const int N = 1e5+10;

// h[]存储每个节点的头节点,无向图使用2N
int h[N],e[2*N], ne[2*N];
// ans记录重心最小值
int idx = 0, n, ans = N;

bool st[N];

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

int dfs(int u)
{
    int size = 0;   // 记录删掉某个节点后的最大连通子图
    st[u] = true;
    int sum = 1;    // 记录根子树的个数

    // 通过头节点遍历整个图
    for(int i=h[u]; i!=-1; i=ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            int s = dfs(j);
            size = max(size,s);
            sum +=s;
        }
    }

    size = max(size, n-sum);//n-sum为向其dfs的父节点所在的联通块的大小
    ans = min(ans,size);    //遍历过的假设重心,最小的最大联通子图节点数
    return sum;
}

int main() {
    memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
    cin >> n; //表示树的结点数

    // 树中是不存在环的，对于有n个节点的树，必定是n-1条边
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); //无向图
    }

    dfs(1); //可以任意选定一个节点开始 u<=n

    cout << ans << endl;

    return 0;
}