「随笔」树上覆盖问题的$O(n)$解法

午睡前的脑洞
同学给我补充了一下

正确性嘛,不敢说。但是至少目前的题我都用这个算法$A$掉了。

树上覆盖问题大致如下:
给出一棵树,每一个关键点可以覆盖周围距离其$\le k$的点,问最少多少个点可以覆盖这棵树。
定义$f[x]$,$f[x]\ge 0$时,表示以$x$的子树中,距离$x$最远的点的距离是。
假如说树是$1 \rightarrow 2, 2 \rightarrow 3$,那么$f[3] = 0, f[2] = 3, f[1] = 2$。如果$f[x] < 0$,代表子树中某个点覆盖到当前点,还剩下的距离是。树还是$1 \rightarrow 2, 2 \rightarrow 3$,如果我们在$3$处添加一个覆盖点,覆盖范围是$2$。$f[3] = -3, f[2] = -2, f[1] = -1$。每原理一个点,能够覆盖的范围就$-1$。当$f[x] = -1$的时候,这个点是最后一个被覆盖到的点。再举个例子,树的形态是$1 \rightarrow 2, 2 \rightarrow 3, 1 \rightarrow 4$,覆盖范围是$2$。(注意,接下来的部分不是求解,仅仅是举例,帮助理解$f[x]$)假如我们在$3$位置添加覆盖点,有$f[3] = -3$。那么转移到$2$,$f[2] = -2$,$f[1] = -1$,但是因为点$4$的存在,$f[x]$会有$1$的正数情况。$1 + (-1) = 0$。并不是$< 0$,我们需要在$1$处再次添加一个点。
看完上面,你应该已经发现,我们规范了几个写法。
当这个点是被覆盖点的时候,$f[x] = - k - 1$,当这个点是最后一个能够被覆盖到的点的时候,$f[x] = -1$,但是当这个点存在一个会使得其为正数的子树时,设$f[v] = t$,$f[x] + t$仅有$< 0$的情况,才能够覆盖到这棵子树。
写法大概如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline void dfs(int x, int fa) {
int t = 0;
for (int i = head[x], to; ~i; i = nxt[i])
if ((to = ver[i]) != fa) {
dfs(to, x);
if (f[to] + 1 >= 0)
f[x] = max(f[x], f[to] + 1);
else
t = min(t, f[to] + 1);
}
if (f[x] + t < 0)
f[x] = t;
else if (f[x] >= k)
++use, f[x] = -k - 1;
}

if (f[root] >= 0) ++use;

这是一个树形$dp$的写法。
代码中,$t$储存的是拥有覆盖作用的子节点,$f[x]$直接储存需要被覆盖的子节点。如果$f[x] + t < 0$,代表可以用子树中某个关键节点覆盖这整颗树,我们就用那个子节点的贡献继续向上走。如果子树中的关键节点不足以覆盖这棵子树,当前点必定会被设定为关键点。则$f[x] = -k - 1$。
贪心证明如下:
从底部开始$dfs$,显然,$dep$越小,能够覆盖的点越多。所以在某个点,如果这个点的父亲能够覆盖其所有子节点,其一定不需要被作为关键点。对于这个点,如果其父亲不能覆盖,那么这个点一定需要被设为关键点。
如果其子节点某个能够覆盖的话,一定不需要其再添加覆盖,因为其父亲节点一定有一个能够覆盖更多的。(咋有点啃老的味道,不过大概就是这个意思)

qwq