题目描述 城镇有 $n$ 个社区，通过 $n-1$ 条道路连接形成一棵树，每条道路有正长度。需要选择恰好 $k$ 个社区修建公园，目标是最小化所有社区到最近公园的最大距离。

形式化：设 $d(i)$ 表示社区 $i$ 到最近公园的距离，要求选择 $k$ 个公园位置，使得 $\max\limits_{1 \le i \le n} d(i)$ 最小。

核心思路

二分答案框架 这是一个典型的最小化最大值问题，适合用二分答案解决。

二分变量：最大距离 $d$

二分范围：$[0, D]$，其中 $D$ 是树的直径（任意两点间最大距离）

判定问题：对于给定的 $d$，是否存在一种选择 $k$ 个公园的方案，使得所有节点到最近公园的距离 $\le d$？

贪心验证算法 对于给定的 $d$，从叶子向根进行贪心：

状态定义 $\text{maxUncovered}[u]$：节点 $u$ 到其子树中最远未覆盖节点的距离

$\text{minCovered}[u]$：节点 $u$ 到子树中最近公园的距离

初始时 $\text{maxUncovered}[u] = 0$，$\text{minCovered}[u] = +\infty$

DFS 过程

对于叶子节点 $u$：

如果父节点方向有公园能覆盖它，则 $\text{maxUncovered}[u] = 0$

否则 $\text{maxUncovered}[u] = \text{到父节点的距离}$

对于内部节点 $u$，处理完所有子节点后：

从子节点 $v$ 传递上来的信息：

$\text{maxUncovered}[u] = \max\limits_{v \in \text{children}[u]} (\text{maxUncovered}[v] + w(u,v))$

$\text{minCovered}[u] = \min\limits_{v \in \text{children}[u]} (\text{minCovered}[v] + w(u,v))$

建公园决策：

如果 $\text{maxUncovered}[u] > d$ 且 $\text{minCovered}[u] > d$，说明必须建公园

如果 $\text{maxUncovered}[u] + \text{minCovered}[u] \le d$，说明已被覆盖

贪心策略：当需要建公园时，在当前位置建公园，然后：

$\text{maxUncovered}[u] = 0$（该子树已完全覆盖）

$\text{minCovered}[u] = 0$（当前位置有公园）

公园计数 $+1$

根节点特殊处理 遍历完整棵树后，如果根节点的 $\text{maxUncovered}[\text{root}] > 0$，还需要在根节点建一个公园。

方案构造 在二分找到最小可行 $d$ 后，重新运行上述 DFS 过程，但这次：

记录所有建公园的决策

当决定在节点 $u$ 建公园时，将该节点编号加入答案集合

算法步骤

预处理：

读入树结构，建立邻接表

计算树的直径作为二分上界

二分搜索：

初始化 $l = 0$, $r = \text{直径}$

当 $l < r$：

$mid = \lfloor (l + r) / 2 \rfloor$

如果 $\text{check}(mid) \le k$，则 $r = mid$

否则 $l = mid + 1$

输出结果：

第一行输出 $l$（最小最大距离）

第二行输出 $\text{buildSolution}(l)$ 得到的 $k$ 个公园位置

复杂度分析

时间复杂度：$O(n \log D)$

每次验证需要 $O(n)$

二分次数 $O(\log D)$，其中 $D$ 是直径

空间复杂度：$O(n)$

正确性说明

贪心策略的正确性基于：

最优子结构：每个子树的最优解可以组合成整棵树的最优解

贪心选择性质：在深度最大的未覆盖节点处建公园是最优的

覆盖半径的单调性：更大的 $d$ 总是更容易满足条件