洛谷P1395 会议 做题反思（2024.3.10）

会议

题目传送门

题目描述

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

输入格式

第一行，一个数 $n$，表示有 $n$ 个村民。

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

输出格式

一行输出两个数字 $x$ 和 $y$。

$x$ 表示村长将会在哪个村民家中举办会议。

$y$ 表示距离之和的最小值。

样例 #1

样例输入 #1

4
1 2 
2 3 
3 4

样例输出 #1

2 4

提示

数据范围

对于 $70\%$ 数据 $n\le 10^3$。

对于 $100\%$ 数据 $n\le 5\times 10^4$。

以下是代码及其解析

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e4 + 10;
int n, cnt = 1, maxn;
int dis[N], dp[N], s[N];
int ne[2 * N], e[2 * N], h[N], idx;
void add(int a, int b) {
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}
void dfs1(int now) {
	s[now] = 1;
	for (int i = h[now]; i; i = ne[i]) {
		int j = e[i];
		if (dis[j])continue;//当前是判断节点“j”是否被搜过
		dis[j] = dis[now] + 1;//这是计算节点“j”距离父节点的距离
		dfs1(j);
		s[now] += s[j];//这里是计算父节点与其树根节点的个数之和
	}
}
void dfs2(int now, int fa) {
	dp[now] = dp[fa] + n - 2 * s[now];//这里是计算距离在节点“now”开会的距离之和
	for (int i = h[now]; i; i = ne[i]) {
		int j = e[i];
		if (j == fa) continue;
		dfs2(j, now);//将“now”更新为父节点，节点“j”更新为开会地点
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);//建立一个无向树
		add(b, a);
	}
	dis[1] = 1;//设“1”为树根，下一个节点距离节点“1”的初始值为 1
	dfs1(1);//从节点“1”开始递归
	for (int i = 1; i <= n; i++)maxn += dis[i];//计算每个离第一个节点的距离之和
	maxn -= n;//计算距离会议地点之和最大的值，为后面做铺垫
	dp[1] = maxn;//毫无疑问，距离第一个节点的距离之和是最大的
	for (int i = h[1]; i; i = ne[i]) {
		int j = e[i];
		dfs2(j, 1);
	}
	for (int i = 1; i <= n; i++) {
		if (dp[i] < maxn) {//找到最小的距离之和
			maxn = dp[i];
			cnt = i;
		}
	}
	printf("%d %d", cnt, maxn);
	return 0;
}

此题涉及到大量模板，说白了就是一个基础深搜的模板题