题解：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 的联通块算在内，否则难以转移）。

转移是显然的。