#include<cstdio>
#define N 50005

int d[N];
int f[N];
int n,cnt;
int size[N];
bool vis[N];
int head[N];

struct Edge{
    int to,nxt;
}edge[N<<1];

void add(int x,int y){
    edge[++cnt].to=y;
    edge[cnt].nxt=head[x];
    head[x]=cnt;
}

void dfs1(int now){
    size[now]=1;
    for(int i=head[now];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(d[to]) continue;
        d[to]=d[now]+1;
        dfs1(to);
        size[now]+=size[to];
    }
}

void dfs(int now,int fa){
    f[now]=f[fa]+n-2*size[now];
    for(int i=head[now];i;i=edge[i].nxt){
        int to=edge[i].to;
        if(to==fa) continue;
        dfs(to,now);
    }
}

signed main(){
    scanf("%d",&n);
    for(int x,y,i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    d[1]=1;
    dfs1(1);
    int maxn=0,idx=1;
    for(int i=1;i<=n;i++) maxn+=d[i];
    maxn-=n;
    f[1]=maxn;
    for(int i=head[1];i;i=edge[i].nxt){
        int to=edge[i].to;
        dfs(to,1);
    }
    for(int i=2;i<=n;i++){
        if(f[i]<maxn) maxn=f[i],idx=i;
    }
    printf("%d %d",idx,maxn);
    return 0;
}

欢迎访问我的博客：blog.chungzh.cn。

前置知识：树的重心 - Zirnc's blog

树的重心有这样的一条性质：树中所有顶点到某个顶点的距离和中，到重心的距离和是最小的。因此，我们只要找到这棵树的重心即为答案。

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> g[50004];
int siz[50004];
int ans = 1, ansdis, anssiz = 50000;
void dfs(int u, int fa) {
	siz[u] = 1;
	int maxs = 0;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (v == fa) continue;
		dfs(v, u);
		siz[u] += siz[v];
		maxs = max(maxs, siz[v]);
	}
	maxs = max(maxs, n-siz[u]);
	if (maxs < anssiz) {
		anssiz = maxs;
		ans = u;
	} else if (maxs == anssiz) {
		ans = min(ans, u);
	}
}
int calcdis(int u, int fa, int d) {
	ansdis += d;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (v == fa) continue;
		calcdis(v, u, d+1);
	}
}
int main()
{
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1, 0);
	calcdis(ans, 0, 0);
	cout << ans << " " << ansdis << endl;
	return 0;
}