题目地址：

https://www.luogu.com.cn/problem/P1395

题目描述：
有一个村庄居住着$n$个村民，有$n-1$条路径使得这$n$个村民的家联通，每条路径的长度都为$1$。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。

输入格式：
第一行，一个数$n$，表示有$n$个村民。
接下来$n-1$行，每行两个数字$a$和$b$，表示村民$a$的家和村民$b$的家之间存在一条路径。

输出格式：
一行输出两个数字$x$和$y$。
$x$表示村长将会在哪个村民家中举办会议。
$y$表示距离之和的最小值。

数据范围：
对于$70\%$数据$n\le 10^3$。
对于$100\%$数据$n\le 5\times 10^4$。

其实就是求树中的一个点，使得其余点与之距离和最小，如果存在多个和最小的点，则取编号最小的那个。

答案即为树的重心，求法参考https://blog.csdn.net/qq_46105170/article/details/113813152。性质的证明参考https://blog.csdn.net/qq_46105170/article/details/125841504。假设我们不知道该性质，也可以求解。

可以两遍DFS解决。设$d[u]$为所有点与$u$的距离之和。以$1$号点为树根，第一遍DFS求出各个子树$v$的节点个数$s[v]$，和所有点距离$1$号点的距离$d[1]$。第二遍DFS的时候，如果$u\to v$，那么$d[v]=d[u]+n-2s[u]$，从而$d[v]$可以由$d[u]$推出来。由于已知$d[1]$，从而可以将$d$数组整个推出来，看一下$d$值最小的点是谁即可。代码如下：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 5e4 + 10, M = N << 1;
int n;
int h[N], e[M], ne[M], idx;
int sz[N], d[N];
int x, y;

void add(int a, int b) {
    
  e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs1(int u, int from, int dist) {
    
  sz[u] = 1;
  d[1] += dist;
  for (int i = h[u]; ~i; i = ne[i]) {
    
    int v = e[i];
    if (v != from) sz[u] += dfs1(v, u, dist + 1);
  }
  return sz[u];
}

void dfs2(int u, int from) {
    
  if (~from) {
    
    d[u] = d[from] + n - 2 * sz[u];
    if (d[u] < y) {
    
      y = d[u];
      x = u;
    } else if (d[u] == y) x = min(x, u);
  }

  for (int i = h[u]; ~i; i = ne[i]) {
    
    int v = e[i];
    if (v != from) dfs2(v, u);
  }
}

int main() {
    
  memset(h, -1, sizeof h);
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    
    int a, b;
    scanf("%d%d", &a, &b);
    add(a, b), add(b, a);
  }

  dfs1(1, -1, 0);
  // 先假设答案为1号点
  x = 1, y = d[1];
  dfs2(1, -1);
  printf("%d %d\n", x, y);
}

时空复杂度$O(n)$。