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_u=ex_v=0\)

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

• 若 \(ex_u=ex_v=1\)

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

• 若 \(ex_u=0,ex_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\)。

• 若 \(ex_u=1,ex_v=0\)

讨论 \(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)\)。