//tree cutting of usaco 04dec,silver
//[C]WSL,zy's source library
#include <cstdio>
#include <cstring>
using namespace std;

int apre[30050],adt[30050],alst[10050],cnt[10050],asz=0,n;
bool v[10050],ans[10050];

int dfs(int x) {
  if (v[x]) return 0;
  v[x]=true;
  for (int tm=alst[x];tm!=0;tm=apre[tm]) 
    cnt[x]+=dfs(adt[tm]);
  ++cnt[x];
  return cnt[x];
}

void check(int x,int ex_rt) {
  if (v[x]) return;
  ans[x]=true;v[x]=true;
  cnt[ex_rt]-=cnt[x];
  cnt[x]+=cnt[ex_rt];
  for (int tm=alst[x];tm!=0;tm=apre[tm]) if (cnt[adt[tm]]*2>n) {ans[x]=false;break;}
  for (int tm=alst[x];tm!=0;tm=apre[tm])
    check(adt[tm],x);
  cnt[x]-=cnt[ex_rt];
  cnt[ex_rt]+=cnt[x];
}

int main() {
  int a,b,fnd=0;
  scanf("%d",&n);
  for (int i=1;i<n;++i) {
    scanf("%d%d",&a,&b);
    ++asz;adt[asz]=b;apre[asz]=alst[a];alst[a]=asz;
    ++asz;adt[asz]=a;apre[asz]=alst[b];alst[b]=asz;
  }
  memset(cnt,0,sizeof cnt);
  memset(v,false,sizeof v);
  dfs(1);
  memset(ans,false,sizeof ans);
  memset(v,false,sizeof v);
  cnt[0]=cnt[1];
  check(1,0);
  for (int i=1;i<=n;++i)
    if (ans[i]) {printf("%d\n",i); fnd=1;}
  if (!fnd) printf("NONE\n");
  return 0;
}

• 解题报告见 ：： http://hi.baidu.com/drcrow/blog/item/1fdf100ea2891a366a60fba2.html (66) linusc 2011-01-16 18:15:56