【每日一题】8月18日题目精讲-MMSet2
题号 NC14250
名称 MMSet2
来源 Wannafly挑战赛1
戳我进入往期每日一题汇总贴~
往期每日一题二期题单
如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
题解
首先我们要知道题目要求的究竟是什么:f[u]是每个点到集合中的点的最大距离，min(f[u])即找到一个点到点集S的最大距离最小——这个点应该出现在点集S中离得最远的两个点xy连线的中点上。
所以问题就转化成了，求点集S里离得最远的两个点的距离。
求一棵树上任意两个点的最长距离（也就是求树的直径）我们一般跑两趟dfs——第一遍以任意一个点为起点，找到离他最远的点，这个点就是直径的一个端点，然后以这个点为起点再dfs一遍找到直径的另一个端点。这里如果每次查询都去搜一遍时间复杂度不允许（单次查询，查询次数没有给出，但是当每次S都不太大的时候查询次数显然很多），但是我们可以用类似的做法找到一个起点：先以1为根维护出每个点的深度，那么S集合里面深度最深的一个点就是最长距离一个端点，然后，我们直接在S里面枚举另外一个点，用两个点深度和减去他们LCA（最近公共祖先）的深度就是他们的距离。
LCA可以用树上倍增求，也可以转化成dfs序+RMQ。
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！
活动奖励：
在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）
本道题目9月1日中午12：00之前写的题解有获得牛币资格~
牛客博客开通方式
- 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
- 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
- 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴
