Author: lllyouo
Date: 20250311
tag: 树的重心
link: https://www.acwing.com/problem/content/848/

问题描述

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;
}