dp[n][2]，维护儿子的联通块数量和父亲的联通块数量。
第一遍dfs求儿子，第二遍dfs求爸爸。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include <string>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include <iomanip>
#define LL long long
#define INF 20000000
#define N 50500
using namespace std;
int n, m, sum, cnt, flag;
int deg[N];
int head[N];
struct Node
{
int v, next;
}; Node edge[N << ];
LL dis[N];
LL dp[N][];//0 fat,1 son
LL mx[N];
void dfs1(int now, int pre)
{
dp[now][] = ;
for (int i = head[now]; i != -; i = edge[i].next)
{
int e = edge[i].v;
if (e == pre) continue;
dfs1(e, now);
dp[now][] += dp[e][];
}
}
void dfs2(int now, int pre)
{
if (pre == -)
{
dp[now][] = mx[now] = ;
}
else
{
dp[now][] = dp[pre][] + dp[pre][] - dp[now][];
mx[now] = dp[pre][] + dp[pre][] - dp[now][];
}
for (int i = head[now]; i != -; i = edge[i].next)
{
int e = edge[i].v;
if (e == pre) continue;
dfs2(e, now);
mx[now] = max(mx[now], dp[e][]);
}
}
void ini()
{
for (int i = ; i <= n; i++)
head[i] = -, flag = ;
cnt = , sum = n;
}
void add(int u, int v)
{
deg[v]++;
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
int main()
{
//cin.sync_with_stdio(false);
while (scanf("%d",&n)!=EOF)
{
ini();
for (int i = ; i <= n; i++)
{
LL a, b;
//cin >> a >> b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
memset(dp, , sizeof(dp));
LL ans = INF;
dfs1(, -);
dfs2(, -);
for (int i = ; i <= n; i++)
ans = min(ans, mx[i]); set<int> ss;
for (int i = ; i <= n; i++)
if (mx[i] == ans) ss.insert(i);
for (set<int>::iterator i = ss.begin(); i != ss.end();)
{
//cout << *i;
printf("%d", *i);
i++;
if (i == ss.end())printf("\n");
else printf(" ");
}
}
return ;
}