3107.txt

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

Source

Problem Id:3107  User Id:fzk 
Memory:3364K  Time:1523MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <vector>
using namespace std;

vector<int> e[51000];
int ans[51000];
int best, n;

int search( int k, int f ) {
	int sum = 0, s=0, t;
	for( int i=0; i<e[k].size(); i++ ) {
		if( e[k][i] != f ) {
			t = search( e[k][i], k );
			if( t > s )
				s = t;
			sum += t;
		}
	}

	if( n-1-sum > s )
		s = n-1-sum;
	if( s < best )
		best = s;
	
	ans[k] = s;
	return sum+1;
}

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

	best = n;

	search( 1, -1 );

	for( i=1; i<=n; i++ )
		if( ans[i] == best )
			printf( "%d ", i );
	return 0;
}