思路：
每個(gè)節(jié)點(diǎn)記錄在它以下的所有孩子的數(shù)目。后序遍歷就比較容易得出結(jié)果了。
#include <stdio.h>
struct node 
{
struct node *next;
int idx;
};
struct node *map[10032], nodes[10032*2];
int N, nodes_cnt, can[10032];
__inline void add(int a, int b)
{
struct node *p = &nodes[nodes_cnt++];
p->idx = b;
p->next = map[a];
map[a] = p;
}
int dfs(int idx, int parent)
{
struct node *p;
int sum, i, res;
sum = 1;
res = 1;
for (p = map[idx]; p; p = p->next) {
if (p->idx == parent)
continue;
i = dfs(p->idx, idx);
if (i > N/2)
res = 0;
sum += i;
}
if (N - sum > N/2)
res = 0;
can[idx] = res;
return sum;
}
int main()
{
int i, a, b;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &N);
for (i = 0; i < N - 1; i++) {
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
dfs(1, 0);
for (i = 1; i <= N; i++)
if (can[i])
printf("%d\n", i);
return 0;
}