arc101C | Ribbon on tree

题意

题目大意解释一下，让你给一颗树结点配对，染色每对点。如果每一条边都有颜色，那么就算一种合法的情况。

---

sol

0正：对于任意

反：存在

显然正难则反。

存在难，所以显然钦定然后容斥。

---

这样大体idea 出来了。

step1

首先发现一件事情,我们可以通过把一颗树，切掉一条边，变成两颗子树，递归分别求解。

这样求出的是不包括 钦定的这条边的合法情况数。

这样显然可以容斥。

\(\texttt{Complexity : }\mathcal{O(2^n)}\).

step2

复杂度在于现在需要决策每一条边选不选。

这样让我们想到类似背包类的 dp。

\(\text{dp}_u(x)\) 表示以 \(u\) 为根的子树，与 \(u\) 相连有 \(x\) 个。