题目描述

树的重心 vector 建立邻接表

#include<bits/stdc++.h>
using namespace std;

int n; 
vector<bool> st;
vector<vector<int>> e;
int ans;

int dfs(int u){
    int res = 0;
    int sum = 1;
    st[u] = true;
    for(auto x : e[u]){
        if(!st[x]){
            int s = dfs(x);
            res = max(res, s);
            sum += s;
        }
    }
    res = max(res, n - sum);
    ans = min(ans, res);
    return sum;
}

int main(){
    cin >> n;
    int a, b;
    e = vector<vector<int>>(n + 1);
    st = vector<bool>(n + 1, false);
    for(int i = 1; i <= n; i ++)
        cin >> a >> b, e[a].push_back(b), e[b].push_back(a);
    ans = INT_MAX;
    dfs(1);
    cout << ans;
    return 0;
}