2019牛客暑期多校训练营（第四场）Ameeting是哪一场比赛？

本文共计412个文字，预计阅读时间需要2分钟。

题目：传送门 > 传送门 + 题目n：给城市有n-1条道路相连，每两个城市之间的道路花费为1。有k个人在k个城市，问这k个人聚集在同一城市的最小花费。

思路：思考官方给出的题解，理解其逻辑，考虑考虑距离最远的两个城市，计算它们之间的距离，然后逐步缩小范围，找到最小花费。

传送门

>传送门<

题意n给城市有n-1条路相连每两个城市之间的道路花费为1有k个人在k个城市问这k个人聚集在同一个城市的最小花费

思路官方给的题解写的挺好理解的

考虑距离最远的两个关键点设它们的距离为dd/2上取整即为答案。

• 必要性这两个人要碰面必然要走至少d/2步。
• 充分性我们取两人路径中和一头距离为d/2上取整的一个点让所有人在这相聚。如 果有一个人在d/2时间内到不了那么它和路径两头中与它远的那一头的距离大于d与 最远的假设矛盾。

找到这样最远的一对点类似找树的直径。可以直接dp也可以采用两遍dfs

从任意一个关键点开始找到离它最远的关键点x再从x开始dfs找到的新的最远点和x形成的就是直径。

当然对着题面直接dp也是可以做的但是比较难写。