(mathcal{Description})
Link.
给定一棵 (n) 个点的树，其中 (2|n)，你需要把这些点两两配对，并把每对点间的路径染色。求使得所有边被染色的方案数，对 (10^9+7) 取模。
(nle5000)。
(mathcal{Solution})
容斥，令 (f(S)) 表示钦定边集 (S) 全部为被覆盖的方案数。显然答案为：
[sum_{Ssubseteq E}(-1)^{|S|}f(S)
]
(S) 的断边相当于把原树切分为联通块，且块内可以任意配对。令 (g(n)) 表示大小为 (n) 的块任意配对的方案数，则：
[g(n)=egin{cases}
[n=2]&nle2\
(n-1)g(n-2)& ext{otherwise}
end{cases}
]
理解上，考虑在 (g(n-2)) 的基础上新加两个点。则可以拆开原来的一对点和这两个点配对，方案数 (frac{n-2}2 imes2)；这两个点亦可直接配对，方案数 (1)。
利用树上 DP 求解，令 (h(u,i)) 表示 (u) 子树内有 (i) 个点与 (u) 连通的方案数。树上背包转移：
[h(u,i)=sum h(v,j)h(w,i-j)
]
特别地，(h(u,0)) 表示 (u) 与父亲被切断，即 (u) 成为独立连通块。这是考虑容斥系数进行转移：
[h(u,0)=-sum h(u,i)g(i)
]
答案即为 (-g(root,0))。
(mathcal{Code})
#include <cstdio>
const int MAXN = 5000, MOD = 1e9 + 7;
int n, ecnt, head[MAXN + 5], siz[MAXN + 5];
int g[MAXN + 5], f[MAXN + 5][MAXN + 5];
struct Edge { int to, nxt; } graph[MAXN * 2 + 5];
inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }
inline void link ( const int s, const int t ) {
graph[++ ecnt] = { t, head[s] };
head[s] = ecnt;
}
inline void solve ( const int u, const int fa ) {
static int tmp[MAXN + 5];
f[u][1] = siz[u] = 1;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ( v = graph[i].to ) ^ fa ) {
solve ( v, u );
for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) tmp[j] = 0;
for ( int j = 0; j <= siz[v]; ++ j ) {
for ( int k = 1; k <= siz[u]; ++ k ) {
addeq ( tmp[j + k], 1ll * f[v][j] * f[u][k] % MOD );
}
}
for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) f[u][j] = tmp[j];
siz[u] += siz[v];
}
}
for ( int i = 2; i <= siz[u]; i += 2 ) addeq ( f[u][0], 1ll * f[u][i] * g[i] % MOD );
f[u][0] = ( MOD - f[u][0] ) % MOD;
}
int main () {
scanf ( "%d", &n );
for ( int i = 1, u, v; i < n; ++ i ) {
scanf ( "%d %d", &u, &v );
link ( u, v ), link ( v, u );
}
g[0] = 1;
for ( int i = 2; i <= n; i += 2 ) g[i] = ( i - 1ll ) * g[i - 2] % MOD;
solve ( 1, 0 );
printf ( "%d
", ( MOD - f[1][0] ) % MOD );
return 0;
}