P4845 Solution

· · 个人记录

link

考虑树形 dp，对于每个 u 直接钦定它的三种可能状态：有灯，没灯但是被其他灯照亮，没灯也没被照亮。

这样钦定会导致一些需要被照亮的点在当前子树中还未被照亮，需要依靠子树外的灯来照亮。称这种点为闲置点。

状态内只需要记录闲置点中最深的到子树根的距离，以及最浅的灯到根的距离，以试图照亮其他子树内的闲置点。

设 dp_{u,i,j,k} 表示，子树 u 内选了 i 个作为灯，深度最深的闲置点距离 u 为 j，最浅的灯距离 u 为 k，的最大价值。

状态数很多，考虑缩减。注意到必然有 j+k>r，否则闲置点可以被这个灯照亮，就不是闲置点了。

这个闲置点最终一定被子树 u 外的某个灯 L 照亮。那么有 dis(u,L)+j\le r。

这揭示 k>dis(u,L)。意味着，灯 L 完爆子树 u 内所有灯，子树 u 内灯能照到的所有子树外的点，L 也能照到。

这说明所有子树 u 内的灯不在未来发挥作用，k 这个信息可以不用记录了。

若子树 u 内存在闲置点，则只需要记录 j；若不存在闲置点，则只需要记录 k。即，j,k 之中只有一个需要记录。

修改 dp 状态，设 dp_{u,ex=0/1,i,j} 表示子树 u 内是否有闲置点，选了 i 个灯，若有闲置点则 j 表示深度最深的闲置点到 u 距离，若无闲置点则 j 表示深度最浅的灯到 u 距离，的最大价值。

树上背包的转移，我们考虑如何合并 u 和一个子树 v 的信息。

枚举 u,v 的 ex,i,j，则新的 ex',i',j' 应该为：

此时只需要更新最近的灯距离，ex'=0,i'=i_u+i_v,j'=min(j_u,j_v+1)。

此时只需要更新最远的闲置点距离，ex'=1,i'=i_u+i_v,j'=max(j_u,j_v+1)。

讨论 u 中灯能不能照到 v 中最远闲置点：

1.若 j_u+1+j_v\le r

此时 u 中灯能照到 v 中最远闲置点，新子树不再有闲置点，ex'=0,i'=i_u+i_v,j'=j_u。

2.若 j_u+1+j_v>r

此时 u 中灯不能照到 v 中最远闲置点，新子树仍有闲置点，ex'=1,i'=i_u+i_v,j'=j_v+1。

讨论 v 中灯能不能照到 u 中最远闲置点：

1.若 j_u+j_v+1\le r

此时 v 中灯能照到 u 中最远闲置点，新子树不再有闲置点，ex'=0,i'=i_u+i_v,j'=j_v+1。

2.若 j_u+j_v+1>r

此时 v 中灯不能照到 u 中最远闲置点，新子树仍有闲置点，ex'=1,i'=i_u+i_v,j'=j_u。

考虑复杂度，树上背包部分是 \Theta(nk)，枚举 j_u,j_v 是 \Theta(r^2)，总共 \Theta(nkr^2)。

注意到若 kr>n，容易发现一定有方案所有点都选上，我们只需要解决 kr\le n 的情况。

这样复杂度是 \Theta(n^2r)。考虑优化枚举 j_u,j_v，我们直接枚举最终的 j'，由于 j' 要么等于 j_u 要么等于 j_v+1，可以讨论等于哪个，另一个的范围对应是一个前缀/后缀最大值。

复杂度 \Theta(n^2)。