自动搬运

查看原文

来自洛谷，原作者为

	SCAU_Lnn 这个家伙很菜，一道题都写不会

搬运于2025-08-24 22:11:47，当前版本为作者最后更新于2020-04-01 11:10:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这道题看得晕？大佬们的题解看不懂？

快看过来~

看完这篇题解你可以获得什么？

1.树上直径求法的详细易懂的证明。

2.一篇启发式的题解帮助你思考。

一.题意

首先看明白这道题的题意，在一棵树上取k个点作为核心城市（群），其他点到核心城市的距离为他们到这些城市的最短距离si。这些最短距离中有一个最大距离，你可以把这个最大距离作为这个核心城市群的参考值ans，要你求所有不同核心城市(群)中ans最小的。（是真的很绕，好好理解一下吧）

二.思路

看懂题目后，我们会发现逻辑有点复杂，首先不知道k个城市要取在哪里，其次又不知道参考值ans怎么求。这个时候我们就可以放弃这道题了

没关系，一步一步来。某大佬曾经说过，遇到复杂的题，先尝试把它变得简单些。 比如说，有k个城市需要考虑，是不是很烦？那么我们先化简一下，只考虑一个城市，那么这个城市会在哪里呢？为什么？（可以先适当的思考一下再继续看题解）

取一个点，要求其他所有的点到这个点的最大距离最小，那我们就要考虑什么时候出现这个最大距离。任取一个点a，它的最远端点是直径的端点，那么最大距离也就是a与两直径端点的距离中的较大值d（什么？你跟我说不懂树的直径？去看下面的求法与证明吧）那么当a作为直径的中点时，可以保证d保持最小值。 （不懂就画图~）

好，我们已经确定一个点的时候要选直径的中点了，（多个点的时候也要选中点，请自行思考）那么接下来要确定其他k-1个点。没头绪？我也没有头绪，Lnn蒟蒻曾说过，没头绪就画图。

好，对于这个图，选了4以后，要选哪个点？首先这个点要与4相连，就只剩10号，5号，3号三位选手了。你可以都试试，选了10号后（非核心城市到核心城市最小距离的最大值）ans为5（4到11），选了5号之后ans为5（4到11），选3号之后ans为4（3到11或者4到12）。选了三号之后ans变小了，所以我们要选的点是3号。好，凭你的直觉和实际距离你继续选，你应该能发现什么。每一次选的时候都有一种贪心的思想在里面，尽量在选完之后使得ans变小。

经过这些思考，你应该能明白要选的点的性质了，总结一下就是按照当前点能走到的最远距离dis降序排序之后，在一个一个选。其中设d[i]为当前深度，maxd[i]为i能走到的最深的深度。那么dis[i]=maxd[i]-d[i]。

按照dis排序之后，前k个点是核心城市，这样子核心城市确定你要找的ans就是其他点到核心城市的距离的最小距离最大值。那么ans如何求得？比如k==3，还是按照上面那个图，排序之后，dis[1]=5,dis[2]=4,dis[3]=3。正确答案是4，是4到12那条路，如果此时你从核心城市下手，会发现很难求，但是如果你换一下思路，从非核心城市下手，只要找到非核心城市中dis最大的那个值，dis[k+1]+1就是你要的答案。

下面给出直径求法和证明。

三.树的直径

求法：任选一点a，保存其dfs遍历到最远的一点b。b为直径的一个端点。 再以b点dfs到最远的一点c。bc即为直径。

证明：三种情况，见图

1.设xy为树上直径，a为直径上一点，b为a找到的最远端点。

既然a找到的最远端点不是x或者y，那么ab>=ax,ab>=ay。 所以只有两种可能：1.（等于时）yb与xy同为直径，所以b为直径端点。2.（大于时）yb>xy，xy不是直径，与假设有误。

2.设xy为直径，a为直径外一点，a在延申时经过xy上一点b。

由证明1知，b继续延申一定会延申到x或者y（直径端点），得证。

3.设xy为直径，a延申到b端点，并且不经过xy，取ab上一点o，xy上一点c。

既然a延申的最远点为b，那么ob>=oc+cy，这条式子改一下，有

co+ob>cy

xc+co+ob>xc+cy

得xb>xy，xy不是直径，与假设有误。

证明完毕，树上一点延申到最远的点是直径端点。

主要是利用反证法证明如果延申到的端点不是直径端点的话，就与假设有误。如果还不懂的话可以参考其他大佬的。

至于代码的话可以参考其他大佬的，思路是差不多的。我的太差了就不拿出来了

如果觉得我菜的话请在评论区刷Lnnnb

如果对你有帮助的话请给我点赞~