洛谷的题意还不如直接看英文……
# 题面
> Linked 洛谷 P3523
点击展开/折叠题面
有一棵 $n$ 个节点的树,树上有一些点是关键点,记关键点集合为 $\mathbb A$;你需要选择树上恰好 $m$ 个不同点,记为点集 $\mathbb B$,最小化下面的式子:
$$ \max_{u\in\mathbb A}\Big\{\min_{v\in\mathbb B}\{\text{dist}(u,v)\}\Big\} $$$n\le 3\times10^5$
# 解析
要求最大值最小,容易想到二分答案。
假设我们二分出的答案是 $d$,这就意味着——任何一个关键点周围距离 $d$ 范围内至少有一个你选择的点。
于是检验 $d$ 是否合法,只需检验“使得每个关键点距离 $d$ 以内都有选择点”的最少选择点个数是否小于 $m$。
那么问题就是怎么求最小需要选多少个点。由于是树形结构,点的深度在一定程度上可以代表距离,不妨贪心地想——
不到deadline不工作, 那么不到必须放置选择点就不放置。
做一遍 DFS,维护 select[u]
和 deepkey[u]
分别表示 $u$ 子树内选择点与 $u$ 的父节点的最小距离、$u$ 子树内的还需要选择点的关键点与 $u$ 的父节点的最大距离;已经决策了 $u$ 子树内哪些点是选择点,并且保证此时 $u$ 子树内的所有关键点都还有可能满足条件。
为什么这样维护?因为 $u$ 子树内还没有已经不合法的关键点,那么选择点越靠上,越有可能给 $u$ 子树外的关键点提供贡献;而 $u$ 子树内还需要选择点的关键点越深,就越有可能不合法。
$u$ 子树中没有选择点时,$select_u=+\infty$;$u$ 子树中没有关键点时,$deepkey_u=-1$。
记 $v$ 是 $u$ 的子节点,$S=\min\{select_v\},D=\{\max\{deepkey_v\}$(若 $u$ 本身是关键点,$D$ 与 $0$ 取 max),如果我们发现:
$S+D\le d$,那么 $u$ 子树中原有的选择点就已经能够满足 $u$ 中的所有关键点,则 $u$ 本身并不需要被选择
$S+D>d$ 且 $D=d$,说明 $u$ 子树中有关键点没有满足,并且如果不选择 $u$,这个关键点就已经不合法了,因此必须选择 $u$,那么此时 $u$ 子树的所有关键点被满足:
- $D\neq -1$ 且 $u$ 是DFS的根节点,$u$ 必须设为选择点;
- 其余情况
这样一遍 $O(n)$ 的 DFS 就可以求出最少需要多少关键点。结合二分可以 $O(n\log n)$ 解决本题。
# 源代码
1 | /*Lucky_Glass*/ |
THE END
Thanks for reading!
> Linked 你别忘-网易云