题目链接:http://poj.org/problem?id=1655
树的重心板子题
#include<iostream> using namespace std; #define maxn 20005 int t,n,cnt,root,maxx,head[maxn<<1],f[maxn],size[maxn]; struct edge{ int next,to; }e[maxn<<1]; void add(int u,int v) { e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt; } void getroot(int now,int fa) { size[now]=1;f[now]=0;//f也是size for(int i=head[now];i;i=e[i].next) { if(e[i].to!=fa) { getroot(e[i].to,now); size[now]+=size[e[i].to]; f[now]=max(f[now],size[e[i].to]); } } f[now]=max(f[now],n-size[now]); if(f[now]<maxx) { root=now; maxx=f[now]; } if(f[now]==maxx&&now<root) root=now; } int main() { cin>>t; while(t--) { cin>>n; for(int i=1;i<=n;i++) head[i]=0; int u,v; cnt=0;maxx=999999999,root=999999999; for(int i=1;i<n;i++) { cin>>u>>v; add(u,v);add(v,u); } getroot(1,0); cout<<root<<" "<<maxx<<endl; } return 0; }