竞码【406】树的重心(树型dp)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
int rt, n, sz[maxn], maxp[maxn];
vector<int>edge[maxn];

inline int read(){
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void print(int x){
    if(x < 0) x = ~x + 1, putchar('-');
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

void dfs(int u, int f){
    sz[u] = 1, maxp[u] = 0;
    for(auto v : edge[u]){
        if(v == f) continue;
        dfs(v, u);
        sz[u] += sz[v];
        maxp[u] = max(maxp[u], sz[v]);
    }
    maxp[u] = max(maxp[u], n - sz[u]);
    if(maxp[u] < maxp[rt]) rt = u;
}

int main(){
    n = read();
    for(int i = 1; i < n; i++){
        int u = read(), v = read();
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    maxp[rt] = n;
    dfs(1, 0);
    for(int i = 1; i <= n; i++)
        if(maxp[i] == maxp[rt]) print(i), putchar(' ');

    return 0;
}