消防局的设立

树上选最少的点,使每个点到某个选中点的距离不超过 2;按深度从大到小,在未覆盖点的爷爷处放消防站。

来源 Luogu P2279 · 标签 贪心 / 树 / 覆盖 / 深度

题目描述

给定一棵 𝑛 个结点的树,边权都为 1。选择尽量少的结点建立消防站,使得每个结点到某个消防站的距离不超过 2。

1≤𝑛≤1000。

题解

以结点 1 为根,求出每个结点的父亲和深度。把结点按深度从大到小排序,并维护每个结点是否已被覆盖。

依次处理结点 𝑣:

  • 若 𝑣 已被覆盖,跳过;
  • 否则在 𝑣 的爷爷处建立消防站;若没有爷爷,则在根结点建立;
  • 把到该消防站距离不超过 2 的所有结点标记为已覆盖。

为什么选爷爷:𝑣 是当前最深的未覆盖点,任何覆盖 𝑣 的消防站都必须距离它不超过 2。在 𝑣 的爷爷处建立消防站,是能覆盖 𝑣 的位置中尽量靠近根的位置,因此能同时覆盖更多尚未处理的上方结点,不会比选择其他位置更差。

每次建站后,直接 DFS 标记距离不超过 2 的结点即可。

复杂度

排序为 𝑂(𝑛log𝑛)。每次建站最多遍历 𝑂(𝑛) 个结点,建站次数不超过 𝑛,最坏时间为 𝑂(𝑛2);空间为 𝑂(𝑛)。

参考

源码位置