记一类树上点覆盖问题

jokersen · 2026-01-14 21:19:32 · 算法·理论

1

有一棵树上有 n 个点，每个点都要被覆盖。

现在可以选一些点放置覆盖器，每个覆盖器可以与它 \le 0 的点，求最少放置数及方案。

这个显然是给每个点放一个覆盖器。

2

1 中的每个覆盖器覆盖的距离换成 1。

DP 输出方案很困难，考虑贪心。

随便选一个点作为根，记 f_x 表示点 x 的父亲。

不难想到按深度从大到小考虑，对于一个已经被覆盖的点直接略过。

现在如果点 x 没被覆盖，显然选 f_x 放覆盖器更优。因为 x 往下的节点已经全被覆盖，放 f_x 比放 x 还能多覆盖一些更上面的点。

对于每个 x，判断是否被覆盖只要看 x,f_x 中有没有覆盖器即可，时间复杂度 \mathcal O(n)

3

1 中的每个覆盖器覆盖的距离换成 k。

可以像 #2 一样贪心放 k 级祖先，但这样判断是否被覆盖是 \mathcal O(k) 的，总时间复杂度为 \mathcal O(nk)。

但可以发现一个性质，就是当 k 大的时候要放覆盖器的数量是不多的。感性理解一下就是当覆盖的范围很大，那么覆盖器就能覆盖很多的点，这样覆盖器的数量就不会多。

严谨一点的话可以考虑最坏情况，即一条链。此时要放覆盖器的数量是 \mathcal O(\dfrac{n}{k}) 的。

所以考虑平衡修改（放覆盖器）与查询（判断是否被覆盖）的复杂度。

对于放覆盖器的点 x，把要标记的点分成在它子树内和其它的两种。

对于第一种，将子树用 dfs 序变为区间。

发现如果只统计上面的覆盖器覆盖下面时，如果能覆盖到更下面的点时一定能覆盖到它。

那么我们设一个 dfs 序列它的意义为：

对于序列中的位置 i，只统计上面的覆盖器覆盖下面时 i 对应的点 x（\operatorname{dfn}(x)=i，\operatorname{dfn}(x) 表示 x 在 dfs 序中的编号）最大能被覆盖到多深，如果这个深度是 \ge x 的深度时 x 就是被覆盖的。

对于第二种，可以看作在 f_x 能覆盖子树中距离 \le k-1 的点，在 f_{f_x} 能覆盖子树中距离 \le k-2 的点，\dots，是类似第一种的情况。

发现对于点 x 上面的覆盖器，我们用第一种统计了。对于 x 下面的覆盖器会被第二种统计，所以是正确的。

那么我们只需要做区间取 \max，单点查询，可以用线段树维护。

这样的话处理第一种是 \mathcal O(\log n) 的，算上第二种一共 \mathcal O(k\log n)，由于只会被修改 \mathcal O(\dfrac{n}{k}) 次，所以总时间复杂度降为 \mathcal O(n\log n)。

注意要判断是否存在 k 级祖先。

4

3 但覆盖点不为全部点/覆盖距离会改变。

只要满足放 k 级祖先一定不劣就可以像 #3 一样做。

例题

P2899

同 #2。

P2279