记录编号	43887	评测结果	AAAAAAAA
题目名称	1143.[石门中学 2009]切割树	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2012-10-15 07:11:57	内存使用	3.41 MiB

#include <iostream>
#include <cstdio>
using namespace std;

int ava=0,ptop[10010],wayto[20010],waynext[20010],v[10010],f[10010];

int maxint(int a,int b)
{
	if (a>b)
		return(a);
	return(b);
}

void getin(int from,int to)
{
	if (ptop[from]==0)
	{
		ava++;
		ptop[from]=ava;
		wayto[ava]=to;
	}
	else
	{
		int poi;
		poi=ptop[from];
		while (waynext[poi])
			poi=waynext[poi];
		ava++;
		waynext[poi]=ava;
		wayto[ava]=to;
	}
}

void fillit(int pos,int last)
{
	int poi;
	poi=ptop[pos];
	while (poi)
	{
		if (wayto[poi]!=last)
		{
			fillit(wayto[poi],pos);
			v[pos]+=v[wayto[poi]]+1;
			f[pos]=maxint(f[pos],v[wayto[poi]]+1);
		}
		poi=waynext[poi];
	}
}

int main(void)
{
	freopen("treecut.in","r",stdin);
	freopen("treecut.out","w",stdout);
	int i,n,a,b;
	bool flag=false;
	cin>>n;
	for (i=1;i<n;i++)
	{
		cin>>a>>b;
		getin(a,b);
		getin(b,a);
	}
	fillit(1,0);
	for (i=1;i<=n;i++)
	{
		if (f[i]*2<=n&&(n-v[i]-1)*2<=n)
		{
			cout<<i<<' ';
			flag=true;
		}
	}
	if (!flag)
		cout<<"NONE\n";
	else
		cout<<endl;
	return(0);
}