P3267 [JLOI2016/SHOI2016] 侦察守卫

· · 题解

讲一下状态是怎么想到的。

显然有一个暴力 dp 是 f_{u,i,j} 表示 u 子树最深的未覆盖的点的深度是 dep_u+i,守卫的最小深度是 dep_u+j。然后暴力转移可以做到 O(nd^4)精细实现可以通过

如果 u 子树内有一个点 x 没被覆盖,同时深度最小的守卫在 y,设最终这个点被 u 子树外的点 z 覆盖,那么 dis(u,x)+dis(u,y)>d\ge dis(u,x)+dis(u,z)\Rightarrow D-dis(u,y)<D-dis(u,z),所以子树外能被 y 覆盖的点一定能被 z 覆盖,不需要记录 y

所以在 u 子树内存在未覆盖的点时只需要记录深度最大的未覆盖点。否则一定全部覆盖,再记录深度最小的守卫。