CF1929E. Sasha and the Happy Tree Cutting

Problem – 1929E – Codeforces

• 无意看一眼标签是 \(dp\) 就一直朝树形状压 \(dp\) 的方向想了一年，发现不是树形 \(dp\)

• 设 \(dp_S\) 为完成集合 \(S\) 内的限制所需要的最少边数

• 把每一对顶点的路径上每条边的值都状压，表示添加这条边可以实现的限制有哪些，记为 \(b_i\)

• 因此有：

• \[dp_S = min\{ dp_{S-b_i} + 1 \} \]

• 但是还没有结束，因为直接这么做是 \(O(nk + 2^kn)\) 的

• 这里需要一个重要结论：不同种类的 \(b_i\) 只有 \(O(k)\) 个

• 考虑把一个 \(L\) 型的限制对拆成两个 \(I\) 型的，种类数一定不会减少

• 而对于每一个加入的 \(L\) 性，显然最多增加两种类型

• 因此最终种类数是 \(O(k)\)

• 因此我们只需要把 \(b_i\) 去重即可做到 \(O(nk + 2^kk)\)