AcWing846 树的重心

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n;
int ans = N;
int st[N];

vector<vector<int>> g(N);

int dfs(int u) { // 返回以u为根的子树的节点数目
    st[u] = 1;

    int size = 0, sum = 1;
    for (int i = 0; i < g[u].size(); i++) {
        int j = g[u][i];
        if (!st[j]) {
            int s = dfs(j);
            size = max(size, s);
            sum += s;
        }
    }
    size = max(size, n - sum);
    ans = min(ans, size);

    return sum;
}

int main() {
    cin >> n;

    for (int i = 1; i <= n - 1; i++) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1);

    cout << ans << endl;

    return 0;
}