【题意】不解释了。
【解题方法】其实这题就是一个树的重心，我用两种方法写的，水题。
【AC 代码 1】
//树的重心 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 20005; const int inf = 0x3f3f3f3f; int head[maxn],tot,mx,mxcnt,n,siz[maxn]; int minn,minid; void init(){ memset(head,-1,sizeof(head)); tot=0; } struct edge{ int v,next; }E[maxn*2]; void addedge(int u,int v){ E[tot].v=v,E[tot].next=head[u],head[u]=tot++; } void dfs(int u,int fa) { siz[u]=1; int he=-1; for(int i=head[u]; ~i; i=E[i].next){ int v=E[i].v; if(v==fa) continue; dfs(v,u); siz[u]+=siz[v]; he=max(he,siz[v]); } he=max(he,n-siz[u]); if(he<minn){ minn=he; minid=u; }else if(he==minn&&minid<u){ minid=u; } return ; } int main() { int T; scanf("%d",&T); while(T--){ scanf("%d",&n); int u,v; init(); for(int i=1; i<n; i++){ scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } minn=inf; dfs(1,-1); cout<<minid<<" "<<minn<<endl; } return 0; } 【AC代码2】 //树形do #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 20010; int head[maxn],tot,dp[maxn],siz[maxn],n; struct edge{ int v,next; }E[maxn*2]; void init(){ memset(head,-1,sizeof(head)); tot=0; } void addedge(int u,int v){ E[tot].v=v,E[tot].next=head[u],head[u]=tot++; } void dfs(int u,int fa){ siz[u]=1,dp[u]=0; for(int i=head[u]; ~i; i=E[i].next){ int v=E[i].v; if(v==fa) continue; dfs(v,u); dp[u]=max(dp[u],siz[v]); siz[u]+=siz[v]; } dp[u]=max(dp[u],n-siz[u]); } int main() { int T; scanf("%d",&T); while(T--){ scanf("%d",&n); init(); for(int i=1; i<n; i++){ int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfs(1,-1); int ans1=1,ans2=dp[1]; for(int i=2; i<=n; i++){ if(dp[i]<ans2){ ans2=dp[i]; ans1=i; } } cout<<ans1<<" "<<ans2<<endl; } }