题解：AT_arc101_c [ARC101E] Ribbons on Tree

直接进行 dp 是简单的，但是复杂度达到了不可接受的 $O(n^3)$。具体就是设 $dp_{i,j}$　表示以 $i$ 为根的子树内，还剩 $j$ 个点没有匹配的方案数。子树之间合并的转移过于复杂，貌似不可以直接优化。

考虑容斥，强制钦定其中若干条边断开（即这条边一定不染色，从而把整棵树分成若干个联通块），其它边没有限制的匹配数。

首先思考如何在知道断掉边的集合时求出对应的方案数。设 $f_i$ 表示联通块大小为 $i$ 时， 块内点两两匹配的方案数，那么可以得出 $f_i$ 简单的递推形式 $f_i = 1 \times 3 \times \dots (i-1)$（需要保证 $i$ 为偶数）。所以如果固定了断掉的边的集合 $E$，分成的 $|E|+1$ 个联通块大小集合是 $S$，那么方案数就是 $(-1)^{|E|+1}\prod_{x \in S} f_x$，还可以把 $-1$ 乘进去方便后面的计算。

解决了上面的问题后，就把原问题转化为：一个大小为 $x$ 的联通块权值为 $-f_x$，现在要把一棵树划分成若干个联通块，定义一种划分的价值为所有联通块的权值的乘积。求所有划分的价值之和。

这个问题可以用树形 dp 解决。设 $f_{i,j}$ 表示以 $i$ 为根的子树内，与 $i$ 联通的联通块大小为 $j$ 的价值之和（不把当前与 $i$ 的联通块算在内，否则难以转移）。

转移是显然的。