\(\mathcal{Description}\)

Link.

给定一棵 \(n\) 个点的树，其中 \(2|n\)，你需要把这些点两两配对，并把每对点间的路径染色。求使得所有边被染色的方案数，对 \(10^9+7\) 取模。

\(n\le5000\)。

\(\mathcal{Solution}\)

容斥，令 \(f(S)\) 表示钦定边集 \(S\) 全部为被覆盖的方案数。显然答案为：

\[\sum_{S\subseteq E}(-1)^{|S|}f(S)
\]

\(S\) 的断边相当于把原树切分为联通块，且块内可以任意配对。令 \(g(n)\) 表示大小为 \(n\) 的块任意配对的方案数，则：

\[g(n)=\begin{cases}
[n=2]&n\le2\\
(n-1)g(n-2)&\text{otherwise}
\end{cases}
\]

理解上，考虑在 \(g(n-2)\) 的基础上新加两个点。则可以拆开原来的一对点和这两个点配对，方案数 \(\frac{n-2}2\times2\)；这两个点亦可直接配对，方案数 \(1\)。

利用树上 DP 求解，令 \(h(u,i)\) 表示 \(u\) 子树内有 \(i\) 个点与 \(u\) 连通的方案数。树上背包转移：

\[h(u,i)=\sum h(v,j)h(w,i-j)
\]

特别地，\(h(u,0)\) 表示 \(u\) 与父亲被切断，即 \(u\) 成为独立连通块。这是考虑容斥系数进行转移：

\[h(u,0)=-\sum h(u,i)g(i)
\]

答案即为 \(-g(root,0)\)。

\(\mathcal{Code}\)

#include <cstdio>

const int MAXN = 5000, MOD = 1e9 + 7;

int n, ecnt, head[MAXN + 5], siz[MAXN + 5];

int g[MAXN + 5], f[MAXN + 5][MAXN + 5];

struct Edge { int to, nxt; } graph[MAXN * 2 + 5];

inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }

inline void link ( const int s, const int t ) {

	graph[++ ecnt] = { t, head[s] };

	head[s] = ecnt;

}

inline void solve ( const int u, const int fa ) {

	static int tmp[MAXN + 5];

	f[u][1] = siz[u] = 1;

	for ( int i = head[u], v; i; i = graph[i].nxt ) {

		if ( ( v = graph[i].to ) ^ fa ) {

			solve ( v, u );

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) tmp[j] = 0;

			for ( int j = 0; j <= siz[v]; ++ j ) {

				for ( int k = 1; k <= siz[u]; ++ k ) {

					addeq ( tmp[j + k], 1ll * f[v][j] * f[u][k] % MOD );

				}

			}

			for ( int j = 1; j <= siz[u] + siz[v]; ++ j ) f[u][j] = tmp[j];

			siz[u] += siz[v];

		}

	}

	for ( int i = 2; i <= siz[u]; i += 2 ) addeq ( f[u][0], 1ll * f[u][i] * g[i] % MOD );

	f[u][0] = ( MOD - f[u][0] ) % MOD;

}

int main () {

	scanf ( "%d", &n );

	for ( int i = 1, u, v; i < n; ++ i ) {

		scanf ( "%d %d", &u, &v );

		link ( u, v ), link ( v, u );

	}

	g[0] = 1;

	for ( int i = 2; i <= n; i += 2 ) g[i] = ( i - 1ll ) * g[i - 2] % MOD;

	solve ( 1, 0 );

	printf ( "%d\n", ( MOD - f[1][0] ) % MOD );

	return 0;

}

巴特西

Solution -「ARC 101E」「AT 4352」Ribbons on Tree

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章