城池和道路可以看作图中的点和边，这些边可以双向到达。因为只有n−1n-1n−1条边，所以是无向无环图。根据题意，我们需要设置军事重镇，让其他点到军事重镇的距离最小。 显然，如果只有一个军事重镇，这个点应该在整个结构的中心。我们把无向图看作树，那么这个点就是树直径的中点。当军事重镇数量增加时，将会从这个点开始往外连接。所以可以用两次深搜的方法找到树的直径，找到直径的中点。将直径中点看作树的根，求出树上每个节点的深度和子树中能达到的最大深度。 子树能达到的最深深度-当前节点深度=当前节点离子树的叶子节点的最远距离 因为当前节点到军事重镇还有1的距离，所以最终距离还要加1。 优先选择距离远的作为军事重镇，那么从大到小排列后前kkk个节点都会被选入，答案就是第k+1k+1k+1个节点离子树叶子节点的最远距离+1 。 另一种思路是逆向思维，选kkk个军事重镇就相当于选n−kn-kn−k个普通城市。我们把选完的普通城市看作删去，那么每一次选择的普通城市都是叶子节点，只有一条边连接。所以每次都删除入度为1的节点，并把相连节点的入度−1-1−1。类似于拓扑排序的写法，用两个队列存储，每轮删除离叶子节点距离相同的点，不断向中心前进。当剩余节点为kkk时，此时离叶子节点的距离即为答案。