正难则反 考虑求 "至少包含一条树边的完美匹配数" 然后用完全图的完美匹配数相减.
无法直接数出 "至少包含一条树边的完美匹配数" 所以这里考虑容斥. 如果能够求出包含树边 A 的完美匹配数 包含树边 B 的完美匹配数 包含树边 C 的完美匹配数... 包含树边 A 和 B 的完美匹配数 包含树边 B 和 C 的完美匹配数 包含树边 C 和 A 的完美匹配数... 包含树边 A B C 的完美匹配数... 这样就可以用容斥求出包含 A 或 B 或 C... 的完美匹配数 即至少包含一条树边的完美匹配数了.
这样的话会有一个问题 每条树边都得枚举 复杂度会炸. 可以发现 恰好包含一条树边 无论是哪一条 完美匹配数都是一样的. 进一步 如果是恰好包含两条树边 那么剩下来的点是可以随便连的 而剩下来的点个数又是一样的 所以 无论选哪两条树边 完美匹配数都是一样的. 那么我只要知道选择两条树边的方案有多少种 然后乘以剩下来的点的匹配方案数 就可以了. 推而广之 现在的任务就是计算 "恰好选择k条树边的方案".
这样问题就在树上了 可以用树形背包解决这个问题.
上面这个方程是 $u$ 被已经合并的树中选了 子树 $v$ 是否被选也不影响.