LINK:潜入行动
初看题感觉很不可做 但是树形dp的状态过于明显。
容易设\(f_{x,j,l,r}\)表示x为根子树内放了j个设备且子树内都被覆盖l表示x是否被覆盖r表示x是否放设备的方案数。
初值我是上面四个状态都设为1 转移分类讨论一下也不困难。
然后需要容斥一下。
复杂度看起来是\(n\cdot k^2\)的 其实是\(n\cdot k\)的 证明 这个我就不口胡了。
当然还有一种转移是只给正确的状态转移 这样就不需要容斥了 可能常数会小一点。
我常数比较大 开o2才能过 枚举的边界注意把握好 这是TLE和AC的区别。