1655.txt

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

#include"iostream.h"
typedef struct edge
{int a;
struct edge *p;
}edge;
edge *a[21000];

int s[21000]; 
int b[21000];
int f[21000];
int fr[21000];
int go;

void find(int from,int to)
{edge *p;
p=a[to];fr[to]=from;
while(p)
{if(p->a==from){p=p->p;continue;}
 find(to,p->a);p=p->p;
}
f[go--]=to;
}





int main()
{int i,j,k,n,t,x,y,m,bl,an;edge *p;
cin>>t;
for(;t>0;t--)
{cin>>n;
for(i=1;i<=n;i++){a[i]=0;s[i]=-1;b[i]=-1;f[i]=-1;}
for(i=1;i<=n-1;i++){cin>>x>>y;p=new edge;p->a=y;p->p=a[x];a[x]=p;
p=new edge;p->a=x;p->p=a[y];a[y]=p;
}
an=n+1;
go=n;
find(0,1);
	
for(k=n;k>=1;k--)
{i=f[k];
	m=1;bl=0;
p=a[i];
while(p)
{if(p->a==fr[i]){p=p->p;continue;}
	if(bl<s[p->a])bl=s[p->a];
 m+=s[p->a];
 p=p->p;}

if(n-m>bl)bl=n-m;
b[i]=bl;
s[i]=m;
if(b[i]<=an){an=b[i];j=i;}
}

cout<<j<<' '<<an<<endl;
}
return 1;
}