ARC101E Ribbons on Tree 题解

ARC101E Ribbons on Tree

题意

• 给定一棵 $n$ 个点的树，保证 $n$ 为偶数。
• 将 $n$ 个点分成 $\frac n2$ 个无序点对。
• 对于每个点对，将树上两点之间的最短路径上的边染色。
• 问有多少种方案使得每条边都被染色。
• $n \le 5 \times 10^3$，答案对 $10^9+7$ 取模。

题解

考虑容斥，设 $f(S)$ 表示强制不覆盖边集 $S$ 中的边的方案数，则答案为 $\sum_{S \subseteq E} (-1)^{|S|} f(S)$。

考虑 $f(S)$ 如何计算，设 $S$ 中的边割掉后将树分成了大小为 $a_{1},a_2,\cdots,a_t$ 这 $t$ 个连通块，则 $f(S) = \prod_{t=1}^t \left[2 | a_i\right]\left(a_i-1\right)!!$，其中 $x!!$ 表示 $x(x-2)(x-4)\cdots$。

考虑树形 DP，设 $f_{i,j}$ 表示考虑 $i$ 的子树，割掉若干条边后 $i$ 所在的连通块大小为 $j$，不包含 $i$ 所在的连通块的贡献总和。

转移就是树上背包，时间复杂度 $\mathcal O(n^2)$。

代码

const int N = 5e3 + 7;
int n, s[N];
vi e[N];
modint p[N], f[N][N], ans;

void dfs(int x, int fa) {
	f[x][1] = s[x] = 1;
	for (int y : e[x])
		if (y != fa) {
			dfs(y, x);
			for (int i = s[x]; i; i--) {
				modint w = 0;
				for (int j = s[y]; j; j--)
					f[x][i+j] += f[x][i] * f[y][j], w -= p[j] * f[y][j];
				f[x][i] *= w;
			}
			s[x] += s[y];
		}
}

int main() {
	rd(n);
	p[2] = 1;
	for (int i = 4; i <= n; i += 2) p[i] = p[i-2] * (i - 1);
	for (int i = 1, x, y; i < n; i++) rd(x, y), e[x].pb(y), e[y].pb(x);
	dfs(1, 0);
	for (int i = 1; i <= n; i++) ans += p[i] * f[1][i];
	print(ans);
	return 0;
}