[ARC101E] Ribbons on Tree 题解

题意：

给定一个大小为 $n(2\le N\le 5000)$ 的树，保证 $n$ 为偶数。

您需要给树上的点两两配对，对于一组点对 $(u,v)$，在树上将 $u\leadsto v$ 的路径染色。

定义一个配对方案合法当且仅当所有边都有颜色，求方案数对 $10^9+7$ 取模。

输入：第一行 $n$ ，接下来 $n-1$ 行 $u,v$ 表示无向边 $u,v$ 。输出：一行答案。

先考虑一个 $\mathcal{O}(n^3)$ 的 dp。

设 $f(u,i)$ 为 $u$ 子树中有 $i$ 个点要向上匹配的方案数。

那么这就是一个树上背包，转移考虑枚举 $u$ 子树内的点数 $i$ ， $v$ 子树内的点数 $j$ 和匹配的对数 $k$

$f_{\rm now}(u,i + j-2k) = \sum_{1\le k \le j \le \min\{\operatorname{size} u,~\operatorname{size} v\}} f_{\rm pre}(u,i)\times f(v,j) \times \binom{i}{k}\binom{j}{k}\times k!$

答案就是 $f(1,0)$ 。不过这样做似乎不好优化。

正难则反，考虑计算不合法的方案数。

首先设 $g(n)$ 为 $n$ 个点两两匹配的方案数，其中 $n$ 为偶数，边界 $g(0)=1$ ，则

$g(n) = 1 \times 3 \times \cdots \times (n - 1) = \prod_{1 \le i \le \frac{n}{2}} (2i-1)$

这个式子很好推，不过还是讲一下吧。

cxy 颇有大数学家费马的风范

记 $n=2k$ ，我们把点标上序号，分为奇偶两列，每次考察 $2k-1$ 和谁匹配。

如果 $2k-1$ 和某个偶点匹配，那会有一个奇点失配并选择剩下那个偶点，方案数为 $k$ 。
如果 $2k-1$ 和某个奇点匹配，那会有一个偶点失配并选择和 $2k$ 匹配，方案数为 $k-1$ 。

那么 $g(n) = (n-1) \times g(n-2) = \prod_{1 \le i \le \frac{n}{2}} (2i-1)$ ，就推出来了。

现在重新设 $f(u,i)$ 为 $u$ 子树内，$u$ 的合法连通块大小为 $i$ 时的方案数。

边界 $f(u,1) = 1$ 。初值是

$f_{\rm now}(u,i + j) = f_{\rm pre}(u,i) \times f(v,j)$

转移钦定 $(u,v)$ 有没有颜色即可

$\begin{aligned} f_{\rm now}(u,i) &\,\operatorname{\big\downarrow}\, f_{\rm pre}(u,i) \times f(v,j) \times g(j) \\[6pt] \end{aligned}$

这里 $a\downarrow b$ 表示 $a \gets a - b$ 。

最后答案就是

$\sum_{i=1}^n f(1,i)\times g(i)$

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(5e3 + 15))
#define addE(u, v) vec[u].push_back(v)

vector<int> vec[N];
int n, f[N][N], g[N], sz[N], tmp[N];
void dfs(int u, int fa)
{
    sz[u] = f[u][1] = 1;
    for(int v : vec[u]) if(v != fa)
    {
        dfs(v, u);
        for(int j = 1; j <= sz[u]; j++) { tmp[j] = f[u][j], f[u][j] = 0; }
        for(int j = 1; j <= sz[u]; j++)
            for(int k = 1; k <= sz[v]; k++)
            {
                add(f[u][j + k], tmp[j] * f[v][k] % mod);
                add(f[u][j], mod - tmp[j] * f[v][k] % mod * g[k] % mod);
            }
        sz[u] += sz[v];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; g[0] = 1;
    for(int i = 2; i <= n; i++) g[i] = g[i - 2] * (i - 1) % mod;
    for(int i = 1, u, v; i < n; i++)  { cin >> u >> v; addE(u, v); addE(v, u);}
    dfs(1, 0); int res = 0;
    for(int i = 1; i <= n; i++) add(res, f[1][i] * g[i] % mod);
    return cout << res << '\n', 0;
}