这道题考察了树的重心的性质，所有点到中心的距离之和是最小的，所以我们一遍dfs求出树的重心，在跑一次dfs统计距离之和。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int INF=0x7f7f7f7f;
4 const int N=50005;
5 int head[N],to[N*2],nxt[N*2],f[N],size[N];
6 int tot,n,center,dis=0;
7
8 void add(int x,int y){
9 nxt[++tot]=head[x];
10 head[x]=tot;
11 to[tot]=y;
12 }
13
14 void dfs(int u,int fa){
15 size[u]=1,f[u]=0;
16 for(int i=head[u];i;i=nxt[i]){
17 int v=to[i];
18 if(v==fa) continue;
19 dfs(v,u);
20 size[u]+=size[v];
21 f[u]=max(f[u],size[v]);
22 }
23 f[u]=max(f[u],n-size[u]);
24 if(f[u]<f[center]||f[u]==f[center]&&u<center) center=u;
25 }
26
27 void dfs2(int u,int fa,int deep){
28 dis+=deep;
29 for(int i=head[u];i;i=nxt[i]){
30 int v=to[i];
31 if(v==fa) continue;
32 dfs2(v,u,deep+1);
33 }
34 }
35
36 int main(){
37 scanf("%d",&n);
38 int x,y;
39 for(int i=1;i<n;i++){
40 scanf("%d%d",&x,&y);
41 add(x,y);add(y,x);
42 }
43 center=0;
44 f[0]=INF;
45 dfs(1,0);
46 dfs2(center,0,0);
47 printf("%d %d\n",center,dis);
48 return 0;
49 }
