消防局的设立
树上选最少的点,使每个点到某个选中点的距离不超过 2;按深度从大到小,在未覆盖点的爷爷处放消防站。来源 Luogu P2279 · 标签 贪心 / 树 / 覆盖 / 深度
题目描述
给定一棵 个结点的树,边权都为 。选择尽量少的结点建立消防站,使得每个结点到某个消防站的距离不超过 。
。
题解
以结点 为根,求出每个结点的父亲和深度。把结点按深度从大到小排序,并维护每个结点是否已被覆盖。
依次处理结点 :
- 若 已被覆盖,跳过;
- 否则在 的爷爷处建立消防站;若没有爷爷,则在根结点建立;
- 把到该消防站距离不超过 的所有结点标记为已覆盖。
为什么选爷爷: 是当前最深的未覆盖点,任何覆盖 的消防站都必须距离它不超过 。在 的爷爷处建立消防站,是能覆盖 的位置中尽量靠近根的位置,因此能同时覆盖更多尚未处理的上方结点,不会比选择其他位置更差。
每次建站后,直接 DFS 标记距离不超过 的结点即可。
复杂度
排序为 。每次建站最多遍历 个结点,建站次数不超过 ,最坏时间为 ;空间为 。