题解

思路

二分所有城镇获知信息所需的时间上限 $x$，判定能否选择不超过 $K$ 个初始城镇，使每个点到最近初始城镇的距离不超过 $x$。

做法

把树任意根化并自底向上处理；对每个子树同时维护从根到最深未覆盖点的距离，以及从根到子树内最近已选点的距离。若最近已选点能够覆盖当前最深未覆盖点，就消去该未覆盖状态；若最深未覆盖距离达到 $x$，便贪心地在当前点放置一个初始城镇。根处理完后若仍有未覆盖点，再在根放置一个。这个选择总是位于某个最深未覆盖点能够被覆盖的最高位置，不会比任何其他方案使用更多初始城镇。

复杂度

一次判定只需按后序遍历整棵树，时间和空间均为 $O(N)$；二分答案后总时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。