POJ 3107

远古版本的oj，提交用c++98，卡vector，必须用链式前向星，绷不住了

#include <stdio.h>
#include <algorithm>
using namespace std;

const int N = 50005;

struct Edge {
    int to, next;
};

Edge edge[N << 1];
int head[N], cnt = 0;

void init() {
    for (int i = 0; i < N; ++i) {
        edge[i].next = -1;
        head[i] = -1;
    }
    cnt = 0;
}

void addedge(int u, int v) {
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

int n;
int d[N], ans[N], num = 0, maxnum = 1e9;

void dfs(int u, int fa) {
    d[u] = 1;
    int tmp = 0;
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == fa) continue;
        dfs(v, u);
        d[u] += d[v];
        tmp = max(tmp, d[v]);
    }
    tmp = max(tmp, n - d[u]);
    if (tmp < maxnum) {
        maxnum = tmp;
        num = 0;
        ans[++num] = u;
    } else if (tmp == maxnum) {
        ans[++num] = u;
    }
}

int main() {
    scanf("%d", &n);
    init();
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1, 0);
    sort(ans + 1, ans + 1 + num);
    for (int i = 1; i <= num; i++) {
        printf("%d ", ans[i]);
    }
    return 0;
}