题解 AT4352 【[ARC101C] Ribbons on Tree】

### 2019-02-06 补档 直接 DP 的话大概是 $\mathcal O (N^3)$ 的，使用容斥原理： 要计算的就是 $\displaystyle \sum_{S \subseteq E} {(-1)}^{|S|} f(S)$，其中 $f(S)$ 表示强制不能覆盖到 $S$ 中的边的方案数。 也就是把 $S$ 内的边都删掉，原树被分割成了若干连通块，每个连通块内部连线的方案数。 显然一个大小为 $n$ 的连通块，任意连线的方案数为 $1 \cdot 3 \cdot 5 \cdot \cdots \cdot (n - 1)$（如果 $n$ 是偶数，$n$ 是奇数的话显然没有方案）。 那么设状态 $dp(i, j)$ 表示考虑 $i$ 的子树，割掉若干条边，$i$ 所在的连通块大小为 $j$，的贡献总和（不算 $i$ 所在连通块的贡献）。 转移也是显然的。 时间复杂度为 $\mathcal O (N^2)$，[评测链接](https://atcoder.jp/contests/arc101/submissions/9924940)。