2378.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <list>
#include <memory.h>

using namespace std;

list<int> e[10000];

int ans[10000] ,n;

void init()
{
	int i,a,b;

	scanf("%d",&n);

	for(i=0;i<n-1;i++)
	{
		scanf("%d%d",&a,&b);
		e[a-1].push_back(b-1);
		e[b-1].push_back(a-1);
	}

	memset(ans, 0, n*sizeof(int));
}

int calc(int s,int f)
{
	int i, total, temp;
	list<int>::iterator iter;
	
	total = 1;

	for( iter = e[s].begin(); iter != e[s].end() ; iter++ )
	if( *iter != f )
	{
		if( ( temp = calc( *iter, s ) ) > ans[s] )
			ans[s] = temp;
		total += temp;
	}

	if( n - total > ans[s] )
		ans[s] = n - total;

	return total;
}

int main()
{
	int i ,answer=0;

	init();
	calc(0,-1);

	for( i=0; i<n ; i++ )
	if( ans[i]*2 <= n )
	{
		printf( "%d\n", i+1 );
		answer++;
	}

	if( answer == 0 ) printf( "NONE\n" );

	return 0;
}