学步园

/*
 * poj2378 AC
 *  一次水过。
 *  简单的树状DP，先做一次dfs算出每个结点的子孙结点总数，包括自己，sum[i]。
 *  再做dfs计算删去每个结点x是否满足条件，即满足：
 *   1) 每个结点的所有子结点i的sum[i]是否小于half。
 *   2) 父结点方向上的结点总数，sum[1]-sum[x]是否小于half(1为树的根结点)。
 *  若满足则为一个解，同时计算每个子结点是否满足。
 *  若某结点不满足条件2，那么其子结点一定不满足条件，
 * 因为sum[1]-sum[x]只会递增，而使子结点一定不满足条件2。
 *
 * */
#include<cstdio>
#include<algorithm>
#include<memory.h>
#define N 10010
using namespace std;

int tree[N<<1],head[N<<1],next[N<<1],sum[N+5];
int ans[N],len = 0,half;
bool vis[N];

long dfs_count(int x)
{
    int i;
    sum[x] = 1,vis[x] = true;
    for(i=head[x];i;i=next[i])
       if(!vis[tree[i]]) sum[x] += dfs_count(tree[i]);
    return sum[x];
}

bool dfs_dp(int x)
{
    vis[x] = true;
    if(sum[1]-sum[x]>half) return false; 
    int i,flag = true;
    for(i=head[x];i;i=next[i])
        if(!vis[tree[i]])
        {
           if(dfs_dp(tree[i])) ans[++len] = tree[i];
           if(sum[tree[i]]>half) flag = false; 
        }
    return flag;
} 

int main()
{
    int n,tot,i,j,k;
//    FILE* fin;
//    fin = fopen("d.in","r");
    scanf("%d",&n);
//    fscanf(fin,"%d",&n);
    for(half=n>>1,tot=0,i=1;i<=n-1;i++) {
//        fscanf(fin,"%d%d",&j,&k);
        scanf("%d%d",&j,&k);
        tree[++tot] = k,next[tot] = head[j],head[j] = tot;
        tree[++tot] = j,next[tot] = head[k],head[k] = tot;
    }
    memset(sum,0,sizeof(sum));
    memset(vis,false,sizeof(vis));
    dfs_count(1);

    memset(vis,false,sizeof(vis));
    if(dfs_dp(1)) ans[++len] = 1;
    if(len==0) 
    {
        printf("NONE\n");
        return 0;
    }

    sort(ans+1,ans+len+1);
    for(i=1;i<=len;i++)
        printf("%d\n",ans[i]);
//    fclose(fin);
    return 0;
}