2021 ICPC 沈阳 L.Perfect Matchings

从 $2n$ 个点的无向完全图中, 删除给定的 $2n - 1$ 条边, 且这些边是一棵树. 问剩下的图的完美匹配数是多少.

$1 \le n \le 2000$

正难则反, 考虑求 “至少包含一条树边的完美匹配数”, 然后用完全图的完美匹配数相减.

无法直接数出 “至少包含一条树边的完美匹配数”, 所以这里考虑容斥. 如果能够求出包含树边 A 的完美匹配数, 包含树边 B 的完美匹配数, 包含树边 C 的完美匹配数… 包含树边 A 和 B 的完美匹配数, 包含树边 B 和 C 的完美匹配数, 包含树边 C 和 A 的完美匹配数… 包含树边 A, B, C 的完美匹配数… 这样就可以用容斥求出包含 A 或 B 或 C… 的完美匹配数, 即至少包含一条树边的完美匹配数了.

这样的话会有一个问题, 每条树边都得枚举, 复杂度会炸. 可以发现, 恰好包含一条树边, 无论是哪一条, 完美匹配数都是一样的. 进一步, 如果是恰好包含两条树边, 那么剩下来的点是可以随便连的, 而剩下来的点个数又是一样的, 所以, 无论选哪两条树边, 完美匹配数都是一样的. 那么我只要知道选择两条树边的方案有多少种, 然后乘以剩下来的点的匹配方案数, 就可以了. 推而广之, 现在的任务就是计算 “恰好选择k条树边的方案”.

这样问题就在树上了, 可以用树形背包解决这个问题.

设 $dp(u, i, 0/1)$ 表示以 $u$ 为根的子树中, 选择 $i$ 条边, 根是否在被选的某一条边上.

根据树形背包 $O(n^2)$ 的合并转移方式, 有方程:

$$tmp(i+j, 0) = tmp(i+j, 0) + dp(u, i, 0) \cdot (dp(v, j, 0) + dp(v, j, 1))$$

$dp(u, i, 0)$ 是当前已合并树的选择方案数, 根在当前以合并树中, 所以不能选上; $dp(v, j, 0/1)$ 是子树 $v$ 中选 $j$ 条边的选择方案数, $v$ 是否被选不影响, 因为不选 $(u, v)$ 这条边.

$$tmp(i+j, 1) = tmp(i+j, 1) + dp(u, i, 1) \cdot (dp(v, j, 0) + dp(v, j, 1))$$

上面这个方程是 $u$ 被已经合并的树中选了, 子树 $v$ 是否被选也不影响.

$$tmp(i+j+1, 1) = tmp(i+j+1, 1), dp(u, i, 0) \cdot dp(v, j, 0)$$

上面这个方程是选 $(u, v)$ 这条边, 所以结果会多出 $1$, 以及 $u$ 不能在已经合并的树中被选, $v$ 不能在子树中被选.

注意 $i(j)$ 枚举到 $\frac{sz}{2}$ 即可, 并且注意可以不选, 即需要枚举到 $0$.

接下来就是求 $2n$ 个点的完美匹配数了. 考虑递推. 设 $f(n)$ 为 $2n$ 个点的完美匹配数, 先把点标号, 拿出最大的那个来, 去和剩下的 $2n - 1$ 个点做一个匹配, 那么还剩下 $2n - 2 = 2(n-1)$ 个点, 这些点的完美匹配个数是 $f(n-1)$. 上面这个枚举方案正好把匹配方式枚举完, 没有遗漏也没有重复. 所以 $f(n) = (2n-1)f(n-1)$.

最后就可以求 “包含’所有k条树边的选择方案’的完美匹配数之和”(不知道怎么表达, 看之前的分析可能更好理解), 为 $(dp(rt, k, 0) + dp(rt, k, 1)) \cdot f(n-k)$. 当 $2 \mid k$ 时, 容斥系数为 $1$; 否则为 $-1$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

int T, n, sz[MAXN<<1], dp[MAXN<<1][MAXN][2], f[MAXN], ans = 0, tmp[MAXN][2];
VI G[MAXN<<1];

void dfs(int u, int f) {
	sz[u] = 1;
	dp[u][0][0] = 1;
	for (int v : G[u]) if (v != f){
		dfs(v, u);
		for (int i = 0; i <= sz[u]/2 + sz[v]/2 + 1; i++)
			tmp[i][0] = tmp[i][1] = 0;
		for (int k = sz[u]/2; k >= 0; k--)
			for (int x = 0; x <= sz[v]/2; x++) {
				tmp[x+k][0] = pls(tmp[x+k][0], mult(dp[u][k][0], pls(dp[v][x][0], dp[v][x][1])));
				tmp[x+k][1] = pls(tmp[x+k][1], mult(dp[u][k][1], pls(dp[v][x][0], dp[v][x][1])));
				tmp[x+k+1][1] = pls(tmp[x+k+1][1], mult(dp[u][k][0], dp[v][x][0]));
			}
		sz[u] += sz[v];
		for (int i = 0; i <= sz[u]/2 + 1; i++)
			dp[u][i][0] = tmp[i][0], dp[u][i][1] = tmp[i][1];
	}
}

int main() {
	scanf("%d", &n);
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i < 2 * n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	dfs(1, 0);

	f[0] = 1;
	for (int i = 1; i <= n; i++)
		f[i] = mult(f[i-1], 2 * i - 1);
	for (int i = 0; i <= n; i++) {
		int k = i&1 ? -1 : 1;
		ans = pls(ans, mult(pls(dp[1][i][0], dp[1][i][1]), k * f[n-i]));
	}
	printf("%d\n", ans);
	return 0;
}