【枚举】bzoj3391 [Usaco2004 Dec]Tree Cutting网络破坏

#include<cstdio>
using namespace std;
#define N 10001
int n;
int v[N<<1],first[N],next[N<<1],en;
void AddEdge(int U,int V)
{
v[++en]=V;
next[en]=first[U];
first[U]=en;
}
int size[N],fa[N];
void dfs(int U)
{
size[U]=1;
for(int i=first[U];i;i=next[i])
if(v[i]!=fa[U])
{
fa[v[i]]=U;
dfs(v[i]);
size[U]+=size[v[i]];
}
}
bool check(int U)
{
if(fa[U]&&n-size[U]>(n>>1))
return 0;
for(int i=first[U];i;i=next[i])
if(v[i]!=fa[U]&&size[v[i]]>(n>>1))
return 0;
return 1;
}
int main()
{
int x,y;
scanf("%d",&n);
for(int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
AddEdge(x,y);
AddEdge(y,x);
}
dfs(1);
bool flag=0;
for(int i=1;i<=n;++i)
if(check(i))
{
printf("%d\n",i);
flag=1;
}
if(!flag)
puts("NONE");
return 0;
}