神仙的容斥题与神仙的树形DP题。
首先搞一个指数级的做法：求总的、能够覆盖每一条边的方案数，通过容斥可以得到( ext{ans}=sumlimits_E{(-1)^{|E|}F(E)})。其中，(F(E))表示钦定删除边集(E)后，其他的连边方案数。显然经过删边操作，这张图被划分成了很多联通块，联通块之间没有连边，方案数就是每个联通快的方案数的成绩。特别地，当(|E|=0)时，这个是总情况数。
如何求解一个联通块内的连边方案数呢？先上式子：( ext{ret}=1 imes 3 imes 5 imes cdots imes (n - 3) imes (n - 1))。如何理解这个式子呢？首先这个“联通块”并不是一定要求联通，因为我容斥的时候只要求某个边集断开，并没有要求其他的都联通呀！所以，随便找第一个点，它可以和(n-1)个点匹配；然后找下一个点，它可以和(n-3)个点匹配······最后总方案树就是它们的乘积。
现在我们有了指数级做法了（就是枚举(E)，时间复杂度(Theta(n^2)))，现在来尝试把它优化到多项式时间复杂度。
一个“联通块”的情况数，仅仅与“点数”的点数有关，这启示我们在 DP 中存下一维状态来存当前点集的大小；每条边都只有选和不选两种情况，这让我们联想到了 0/1 背包。
设 (f_{u,i,0/1}) 表示，(u)这个子树，跟(u)结点连着的“联通块”大小是(i)，此时还未乘上(i)这个联通块的情况数的总情况数（也就是把这个子树删到只剩下(i)个点，不考虑(i)内部情况的总情况数）。显然这时(f_{u,i,0/1})再乘上(g[i])就是总情况数((g[i]=1 imes 3 imes cdots imes (i - 3) imes (n - 1))）。
转移的时候，考虑怎么合并把(v)合并到(father_v)上面；我们的目的是优化(Theta(n^2))枚举边集，所以看这条边钦定删掉和不钦定删掉两种情况，方程分别是：
上面那个方程的含义是，不钦定删除 <v,fat> 那条边，那么它们下面的总情况数是它们的乘积；下面那个方程的意思是，不选这条边，那么下面的方案数要乘上(v,b)的总方案数，即(f imes g)。
最终的答案就等于(sumlimits_{i=1}^n{f_{1,i,0} - f_{1, i, 1}})。
总结一下，这里有几个重要的点：
1.转化为容斥的问题。
2.结合情况数只与结点数有关和边的出现与否只有两种情况，设计类似于 0/1 背包的 DP 方法。
3.树形 DP 不一定是考虑怎么从子节点们一次性推出父亲，还可以考虑怎么把子节点依次并进父亲的答案里面，这种 DP 的实现，需要把 DP 数组的其中一维拷贝一遍，具体实现看下面：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 5e3 + 1e2;
const int mod = 1e9 + 7;
int n, f[maxn][maxn][2], g[maxn], sze[maxn];
vector<int> T[maxn];
void dfs(int x, int fa)
{
int tmp[maxn][2];
memset(tmp, 0, sizeof tmp);
//cout << "HH" << endl;
//cout << x << endl;
sze[x] = 1;
f[x][1][0] = 1;
for (auto s : T[x])
{
if (s == fa) continue;
dfs(s, x);
for (int i = sze[x]; i; i--)
{
for (int j = sze[s]; j; j--)
{
for (int a = 0; a < 2; a++)
{
for (int b = 0; b < 2; b++)
{
(tmp[i + j][a ^ b] += (LL)f[x][i][a] * f[s][j][b] % mod) %= mod;
(tmp[i][a ^ b ^ 1] += (LL)f[x][i][a] * f[s][j][b] % mod * g[j] % mod) %= mod;
}
}
}
}
sze[x] += sze[s];
for (int i = 0; i <= sze[x]; i++)
{
for (int j = 0; j < 2; j++)
{
f[x][i][j] = tmp[i][j];
tmp[i][j] = 0;
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
T[u].push_back(v);
T[v].push_back(u);
}
g[0] = 1;
for (int i = 2; i <= n; i += 2)
{
g[i] = (LL)g[i - 2] * (i - 1) % mod;
}
dfs(1, 0);
int ans = 0;
for (int i = 1; i <= n; i++)
{
(ans += ((LL)f[1][i][0] - f[1][i][1] + mod) * g[i] % mod) %= mod;
}
cout << ans << endl;
return 0;
}