poj2378

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=1e4+10;
vector<int> e[maxn];
int vis[maxn];
int ans[maxn],cnt;
int v[maxn];
int n;
int dfs(int x)
{
    v[x]=1;
    int sum=1;
    int childmax=0;
    for(int i=0; i<e[x].size(); i++)
    {
        int y=e[x][i];
        if(v[y]==1) continue;
        int dian=dfs(y);
        sum+=dian;
        childmax=max(childmax,dian);
    }
    if(childmax<=n/2&&(n-sum)<=n/2)
        ans[++cnt]=x;
    return sum;
}
int main()
{

    scanf("%d",&n);
    for(int i=1; i<=n-1; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        e[a].push_back(b);
        e[b].push_back(a);
        vis[b]=1;
    }
    int root;
    for(int i=1; i<=n; i++)
    {
        if(vis[i]==0)
        {
            root=i;
            break;
        }
    }
//    printf("root=%d
",root);
    dfs(root);
    sort(ans+1,ans+1+cnt);
    for(int i=1; i<=cnt; i++)
    {
        if(i!=cnt) printf("%d
",ans[i]);
        else printf("%d",ans[i]);
    }
}