-
无意看一眼标签是 \(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)\)