【题目来源】
洛谷：P1395 会议 - 洛谷
【题目描述】
有一个村庄居住着 \(n\) 个村民，有 \(n-1\) 条路径使得这 \(n\) 个村民的家联通，每条路径的长度都为 \(1\)。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。
【输入】
第一行，一个数 \(n\)，表示有 \(n\) 个村民。
接下来 \(n-1\) 行，每行两个数字 \(a\) 和 \(b\)，表示村民 \(a\) 的家和村民 \(b\) 的家之间存在一条路径。
【输出】
一行输出两个数字 \(x\) 和 \(y\)。
\(x\) 表示村长将会在哪个村民家中举办会议。
\(y\) 表示距离之和的最小值。
【输入样例】
4
1 2
2 3
3 4
【输出样例】
2 4
【算法标签】
《洛谷 P1395 会议》 #树的重心# #福建省历届夏令营#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 50005, M = N * 2;
int n, u, v, cnt[N], maxx[N], minn=1e9;
int h[N], e[M], ne[M], idx;
int root, ans;// 添加无向边
void add(int a, int b)
{e[idx]=b, ne[idx] = h[a], h[a]=idx++;
}// 深度优先搜索，计算子树大小和最大子树大小
void dfs(int u, int fa)
{cnt[u]=1; // 当前节点自身for (int i=h[u]; i!=-1; i=ne[i]) // 遍历所有邻接点{int j = e[i];if (j==fa) continue; // 跳过父节点dfs(j, u); // 递归遍历子树cnt[u]+=cnt[j]; // 累加子树大小maxx[u] = max(maxx[u], cnt[j]); // 更新最大子树大小}maxx[u]=max(maxx[u], n-cnt[u]); // 考虑父节点方向的子树大小
}// 深度优先搜索，计算所有节点到重心的距离之和
void dfs2(int u, int fa, int dist)
{for (int i=h[u]; i!=-1; i=ne[i]) // 遍历所有邻接点{int j = e[i];if (j==fa) continue; // 跳过父节点ans += dist+1; // 累加距离（当前节点到子节点的距离是dist+1）dfs2(j, u, dist+1); // 递归遍历，距离增加1}
}int main()
{memset(h, -1, sizeof(h)); // 初始化邻接表头指针cin >> n; // 读入节点数// 读入边的信息，构建无向图for (int i=1; i<n; i++){cin >> u >> v;add(u, v), add(v, u); // 添加双向边}// 第一次DFS，计算每个节点的子树信息和最大子树大小dfs(1, 0);// 寻找重心（最大子树大小最小的节点）for (int i=1; i<=n; i++){if (maxx[i]<minn) // 找到更优的重心{root = i; // 更新重心节点编号minn = maxx[i]; // 更新最小最大子树大小}}cout << root << " "; // 输出重心节点编号// 第二次DFS，计算所有节点到重心的距离之和dfs2(root, 0, 0);cout << ans << endl; // 输出距离之和return 0;
}
【运行结果】
4
1 2
2 3
3 4
2 4