[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;
}