#include <iostream>
#include <vector>
using namespace std;
#define N 20010
int n;
vector<int> map[N];
bool visite[N];
int ans, node;
int dfs( int u )
{
int total= 0;
int curmax= 0;
for( size_t i= 0; i< map[u].size(); ++i )
{
int v= map[u][i];
int t;
if( !visite[v] )
{
visite[v]= true;
t= dfs( v );
total+= t;
if( t> curmax ) curmax= t;
}
}
if( n- 1- total> curmax ) curmax= n- 1- total;
if( curmax< ans ) ans= curmax, node= u;
else if( curmax== ans && u< node ) node= u;
return total+ 1;
}
int main()
{
int test;
scanf("%d",&test);
while( test-- )
{
scanf("%d",&n );
int a, b;
for( int i= 1; i< n; ++i ){
scanf("%d%d",&a,&b );
map[a].push_back(b);
map[b].push_back(a); }
ans= 1<<30;
memset( visite, false, sizeof(visite) ); visite[1]= true;
dfs( 1 );
printf("%d %d\n", node, ans );
for( int i= 0; i<= n; ++i ) map[i].clear();
}
return 0;
}
posted on 2009-04-19 20:45
Darren 閱讀(349)
評(píng)論(0) 編輯 收藏 引用