[ARC101E] Ribbons on Tree 题解

其实算一道好题了。

首先考虑不相关的 simple 的 dp。平凡的想法是设 \(dp_{i,j}\) 表示 \(i\) 子树内有 \(j\) 个点还需要向上转移的方案数。转移式大概是个 \(dp_{x,i+j}=dp_{y,i+j-1}+(dp_{p,i-1}+dp_{q,j-1})\) 之类的东西。这样的 dp 是 \(O(n^3)\) 的，并且难以优化。于是考虑放弃这个想法。

由于 \(n\le5000\)，图上问题我们考虑容斥来计算。考虑这个常见的容斥：设 \(s(i)\) 表示 钦定了 \(i\) 条边不选择，而不管其它边的方案数。容易得到 \(\text{ans}=\sum s(i)(-1)^i\)。

考虑钦定边不选择的操作如何实现。考虑钦定一些边不选之后树会变成一些个连通块。这样一来我们尝试考虑依据连通块来 dp。那么对于每一个连通块里的点我们是可以任意连边的，并且容易得到对于 \(n\) 个点的树两两任意连边方案数是 \(\sum_{i=1}^{\frac{n}{2}}2\times i-1\) 的。现在考虑设出状态。

对于图上计数问题通常的策略是枚举 \(1\) 号点的连通块大小，那么我们尝试在本题中这么做。于是设 \(dp_{i,j}\) 表示 \(i\) 子树中 \(i\) 的连通块大小为 \(j\) 而不计这个连通块内部的方案数，即不考虑 \(s(j)\)。

那么转移方程就是好得到的，我们枚举点 \(x\) 的 \(i=siz_x\)，\(y\) 的 \(j=siz_y\)，于是枚举 \((x,y)\) 选还是不选。如果选择做正的贡献，反之做负的贡献，通过这样的操作容斥计算方案数即可。

对于时间复杂度，事实上枚举 \(i,j\) 的操作的复杂度相当于对树上的每一个点对 \((x,y)\) 在 LCA 处枚举了一遍，因此时间复杂度 \(O(n^2)\)。

整体上本题充分地考察选手综合运用容斥和 dp 知识解决问题的能力，环环相扣，解题逻辑清晰。是一道好题。

代码：

#include <bits/stdc++.h>
#define N 5005
#define int long long
#define mod 1000000007
using namespace std;
int n;
struct Node {
	int to, nxt;
} e[N << 1];
int head[N], cnt;
void add(int u, int v) {
	e[++cnt].to = v;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
int f[N][N], g[N];
int bas[N];
int siz[N];
void dfs(int x, int fa) {
	siz[x] = f[x][1] = 1;
	for (int i = head[x]; i; i = e[i].nxt) {
		int y = e[i].to;
		if (y == fa)
			continue;
		dfs(y, x);
		for (int j = 1; j <= siz[x]; j++)
			for (int k = 1; k <= siz[y]; k++) {
				if (j + k <= n)
					g[j + k] = (g[j + k] + f[x][j] * f[y][k] % mod) % mod;
				g[j] = (g[j] - f[x][j] * f[y][k] % mod * bas[k] % mod + mod) % mod;
			}
		siz[x] += siz[y];
		for (int j = 1; j <= siz[x]; j++)
			f[x][j] = g[j], g[j] = 0;
	}
}
int ans;
signed main() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%lld%lld", &x, &y);
		add(x, y);
		add(y, x);
	}
	bas[0] = 1;
	for (int i = 2; i <= n; i += 2)
		bas[i] = bas[i - 2] * (i - 1) % mod;
	dfs(1, 0);
	for (int i = 2; i <= n; i += 2)
		ans = (ans + f[1][i] * bas[i] % mod) % mod;
	cout << ans << "\n";
	return 0;
}