前言
此片题解大致按照笔者做题思路进行讲解。
简要题意
有一棵树，树上有偶数个节点。你需要给这些点两两配对，一组已经配对的点会将两点之间的树边进行一次覆盖。一组合法方案需要满足树上所有边都被覆盖至少一次，求合法方案数。
数据范围：\(n\le5000\)。
思路
首先我们去观察题目性质，发现没有什么特殊的地方。我最开始只想到一个非常暴力的 \(dp\)，设 \(f_{u,i}\) 表示以 \(u\) 为根的子树内有 \(i\) 个点已经匹配好的方案数。但是当我去考虑转移时，我发现他有很多种情况：
- \(u\) 一个儿子的子树内互相匹配，但是需要有一个点与外面的点匹配（不然这个子树与 \(u\) 之间的边就无法被覆盖）；
- 一个子树内的点向 \(u\) 的其他子树匹配；
- 一个子树的点向 \(u\) 子树以外的点匹配。
或许还有一些没有罗列出来，但反正就是不可做。于是我们正难则反，考虑先求出不合法的情况，然后容斥做。
题解
如何求不合法的情况呢？我们可以通过钦定一些边不覆盖来容斥。比如当我计算到以 \(u\) 为根的子树时，我就去枚举 \(u\) 所在的连通块的大小，对于一个 \(u\) 的儿子 \(v\)，分讨一下连通块是否包括 \(v\)。
具体的，我们设 \(f_{u,i}\) 表示以 \(u\) 为根的子树，\(u\) 所在连通块大小为 \(i\) 的方案数。对于 \(v\) 在连通块的时候，有转移：
\[f_{u,i-j}\times f_{v,j}\rightarrow f_{u,i},v\in{\operatorname{son}_u,j<i} \]若 \(v\) 与 \(u\) 之间的边不覆盖，则有：
\[f_{u,i}\times f_{v,j}\rightarrow f_{u,i+j} \]你乍一看这不就是树上背包吗？时间复杂度 \(O(n^2)\)，可以通过此题！
现在我们已经基本找出状态转移的方程，但现在我们还需要思考一个问题：
一个点数为 \(k\) 的连通块，将里面的点不重不漏两两匹配的方案数
首先对于 \(k\) 为奇数的时候是无贡献的；所以只用考虑 \(k\) 为偶数的情况。考虑递推求解答案，设 \(s_k\) 表示点数为 \(k\) 的贡献。对于一个点，我有 \(k - 1\) 种选择方案，而剩下的 \(k-2\) 个点的方案是 \(s_{k-2}\)，固可得递推式：\(s_{k}=(k-1)\times s_{k-2}\)。
但考虑到我们只是没有考虑这些方案中会有的不合法情况，所以需要稍微容斥一下，在转移的时候还需要给一个 \((-1)^k\)。
然后看到之前的 \(dp\)，我们发现对于第一种情况合并两个连通块似乎不好计算方案，于是我们改写状态，设 \(f_{u,i}\) 表示以 \(u\) 为根的子树，\(u\) 所在连通块大小为 \(i\) 时不考虑 \(u\) 所在连通块中匹配情况的方案数，这样在合并两个连通块时我们就直接把系数乘上就行，所以最后第一种情况的转移式为：
\[f_{u,i}\leftarrow f_{u,i-j}\times f_{v,j}\times(-s_i) \]最后答案就是 \(\sum\limits_{i}f_{1, i}\times s_i\)。
代码
void dfs(int u, int fa){
sz[u] = f[u][1] = 1;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to; if(v == fa)continue;
dfs(v, u); copy(f[u], f[u] + 1 + sz[u], g);
fill(f[u], f[u] + 1 + sz[u], 0);
for(int j = 1; j <= sz[u]; ++j)for(int k = 1; k <= sz[v]; ++k)
f[u][j] = del(f[u][j], mul(mul(f[v][k], s[k]), g[j])),
f[u][j + k] = add(f[u][j + k], mul(g[j], f[v][k]));
sz[u] += sz[v];
}
}