【题解】LJJ 爱数树 树上 DP 洛谷 P4845 -永无岛

题目链接

题目简述

给定一个点带权的树，用观测半径为 $r$的摄像头放在节点处，要求覆盖的点的点权和尽量大。求这个最大值。

前言

本题是洛谷 2018 年 8 月 3 号的一场比赛 (链接)的 T2。
我在 QQ 上问了出题人两个小时才懂…… 在这里对他细致耐心的讲解表示感谢。

个人对题目的理解

这道题是一个经典类型的变种，原本是给定一棵树和一些摄像头，每个摄像头有一个观测半径 r，让你覆盖树上所有点，并且最小化放的摄像头的个数 (当然这个也有 $\Theta(n)$的贪心写法)。如果给每个点放摄像头附一个 $cost$值并且只要求覆盖若干个关键点的话就是另外一道题目，而这道题是反了过来，固定了摄像头的个数，要求你最大化被覆盖的点的权值和。

暴力 DP

首先，我们并不能找到什么常规的套路来设状态，因为我们发现，判断一个摄像头的贡献是不太容易的。那么可以换一个角度，我们站在每一个点的角度来考虑。一个点无非三种状态：1. 不计入答案。2. 在这个点上放了摄像头。3. 这个点期望会被某个摄像头覆盖到。1 和 2 比较好操作，至于 3 的话，可以记录一个当前子树内深度最小的摄像头来完成。
这样我们就有了一个初步的想法：
令 $f[i][j][k]$表示 i 号节点的子树内，放了 j 个摄像头，最浅的摄像头的深度为 k, 的最大收益。
但是这样只是解决了一个点被它子树内的一个摄像头覆盖，那么要如何表示一个点被它子树外的一个摄像头覆盖？
这时候有一个转化：我们先把他计入答案，然后等会儿再让上方的一个摄像头来覆盖，具体操作是再记录一个维度表示当前期望被覆盖却还没有被覆盖的点中深度最大的点的深度。
令 $f[i][j][k1][k2]$表示 i 号节点的子树内，放了 j 个摄像头，最浅的摄像头的深度为 k1, 当前子树内期望被覆盖却还没有被覆盖的点中深度最大的点的深度是 k2，的最大收益。转移的时候树上背包就好了，记得 k1 是取 min，k2 是取 max。此做法复杂度 $\Theta(n\times k \times r^2)$，根据出题人的说法可以过 40 分。

优化一

先给出结论: 当 k1+k2 大于 r 时，k1 不需要存；当 k1+k2 小于等于 r 时，k2 不需要存。
后一个显然，因为当 k1+k2 小于等于 r 时，实际意义就是子树内的所有的期望被覆盖的点都可以被子树内的摄像头覆盖，这时候 k2 本质上是不存在的，因为子树内不存在期望被覆盖却还没有被覆盖的点。
至于前一个的话，考虑，若子树内有一个期望被覆盖却还没有被覆盖的点a，最浅的摄像头是b，当前子树根节点为i, 之后覆盖a的点为c，那么我们有：1.$dis(i,a)+dis(i,b)>r$,2.$dis(i,a)+dis(i,c)=r$, 可得 $dis(i,b)>dis(i,c)$，所以有这样一个结果：对于子树外的点，b 能覆盖的，c 一定能覆盖，而子树内的点的贡献已经被考虑过了，故存 b 的深度，即 k1 是不必要的。
所以我们知道了，第 3 维和第 4 维可以根据刚刚推出来的结论压成一个大小为 r 的维度，此时我们把复杂度降到了 $\Theta(n\times k \times r)$。

优化二

这个优化的原理简单的惊人：当 $k \times r > n$时，直接输出 $\sum val_{i}$。
原理的证明比较显然，每一次放摄像头都在深度最大的点放，若最大深度小于 r 就在根放，这样每一次都一定至少覆盖了 r 个点，k 个就至少覆盖了 $k×r$个点。
所以直接特判 $k \times r > n$，对于 $k \times r \leq n$做一遍 DP 就好了。
复杂度 $\Theta(n\times k \times r) \leq \Theta(n^{2})$。

Code??

反正是退役选手，口胡一下算了 (我才不会告诉你是因为我写挂了到现在都没调出来)。程序的话，给个标程链接算了：
题解/标程
如果还有问题欢迎来问！QQ 挂在个人说明里面。