[ARC101E]RibbonsonTree(容斥，dp)

Description

给定一棵有 \(n\) 个节点的树，满足 \(n\) 为偶数。初始时，每条边都为白色。

现在请你将这些点两两配对成 \(\frac{n}{2}\) 个无序点对。每个点对之间的的路径都会被染成黑色

求有多少种配对方案，使得树上没有白边？

\(n\le 5000\)

Solution

法一：

树上的路径很难直接考虑。

有一种容斥的做法：记边集为 E ，枚举 T 子集中的边强制为白边，其余的不作限制， 那么：

\[
Ans = \sum_{T\subseteq E} (-1) ^ {T} F(T)
\]

\(F(T)\) 为强制 T 的边为白边的方案数。

把 T 删掉后不难发现树变成了若干个联通块，显然这若干个连通块是独立的。

对于一个大小为 n 的连通块，两点随便配对的方案数是 \((n - 1) * (n - 3) * \cdots * 1\)，记为 \(g(n)\) 。

然而暴力枚举 T 复杂度过高，考虑树型 dp ，需要知道的状态是 u 当前所在联通块大小以及容斥系数(即 T 的奇偶)。

设 \(dp[u][i][0/1]\) 为 u 子树内，u 所在联通块大小为 i ，T 的奇偶性是 0 / 1 的方案数。

转移就合并 u 的子树 v ，同时考虑 这条边是否选入 T 集合，有点做 01 背包的感觉。

\[
dp[v][i][a]\times dp[u][i][b] \rightarrow dp&＃39;[u][i + j][a\oplus b]\dp[v][j][a]\times dp[u][i][b]\times g[i] \rightarrow dp&＃39;[u][i][a\oplus b\oplus 1]
\]

最后答案就是 \(|T|\) 为偶数的 - \(|T|\) 为奇数的。

\[
Ans = \sum_{i = 1} ^ n (dp[root][i][0] - dp[root][i][1]) \times g[i]
\]

#include
#include
#include
#include
#include
using namespace std;
#define End exit(0)
#define LL long long
#define mp make_pair
#define SZ(x) ((int) x.size())
#define GO cerr <<"GO" <#define DE(x) cout <<#x <<" = " <#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
void proc_status()
{
freopen("/proc/self/status","r",stdin);
string s; while(getline(cin, s)) if (s[2] == &＃39;P&＃39;) { cerr <}
template inline T read()
{
register T x = 0;
register char c; register int f(1);
while (!isdigit(c = getchar())) if (c == &＃39;-&＃39;) f = -1;
while (x = (x <<1) + (x <<3) + (c ^ 48), isdigit(c = getchar()));
return x * f;
}
template inline bool chkmin(T &a,T b) { return a > b ? a = b, 1 : 0; }
template inline bool chkmax(T &a,T b) { return a const int maxN = 5000 + 2;
const int mod = 1e9 + 7;
vector adj[maxN + 2];
int g[maxN + 2], n, size[maxN + 2];
int dp[maxN + 2][maxN + 2][2];
void input()
{
n = read();
for (int i = 1; i {
int u = read(), v = read();
adj[u].push_back(v), adj[v].push_back(u);
}
}
void dfs(int u, int f)
{
static int tmp[maxN + 2][2];
size[u] = 1;
dp[u][1][0] = 1;
for (int v : adj[u])
if (v != f)
{
dfs(v, u);
for (int i = 0; i <= size[u]; ++i)
for (int j = 0; j <= size[v]; ++j)
for (int a = 0; a <2; ++a)
for (int b = 0; b <2; ++b)
{
(tmp[i + j][a ^ b] += (LL) dp[v][j][a] * dp[u][i][b] % mod) %= mod;
if (!(j & 1))
(tmp[i][a ^ b ^ 1] += (LL) dp[v][j][a] * dp[u][i][b] % mod * g[j] % mod) %= mod;
}
size[u] += size[v];
for (int i = 0; i <= size[u]; ++i)
for (int j = 0; j <2; ++j)
dp[u][i][j] = tmp[i][j], tmp[i][j] = 0;
}
}
void solve()
{
g[0] = 1;
for (int i = 2; i <= n; i += 2) g[i] = (LL) g[i - 2] * (i - 1) % mod;
dfs(1, 0);
int ans = 0;
for (int i = 1; i <= n; ++i)
(ans += ((LL) dp[1][i][0] - dp[1][i][1] + mod) * g[i] % mod) %= mod;
cout <}
int main()
{
#ifndef ONLINE_JUDGE
freopen("xhc2.in", "r", stdin);
freopen("xhc2.out", "w", stdout);
#endif
input();
solve();
return 0;
}


法二：

还是基于上面的容斥。

设 \(dp[u][i]\) 为 u 子树内还有 i 个点没有匹配，但考虑了容斥系数的答案。

合并子树后注意下 \(dp[u][0]\) 的转移要乘以 -1 的容斥系数（根除外）

#include
#include
#include
#include
#include
using namespace std;
#define End exit(0)
#define LL long long
#define mp make_pair
#define SZ(x) ((int) x.size())
#define GO cerr <<"GO" <#define DE(x) cout <<#x <<" = " <#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
void proc_status()
{
freopen("/proc/self/status","r",stdin);
string s; while(getline(cin, s)) if (s[2] == &＃39;P&＃39;) { cerr <}
template inline T read()
{
register T x = 0;
register char c; register int f(1);
while (!isdigit(c = getchar())) if (c == &＃39;-&＃39;) f = -1;
while (x = (x <<1) + (x <<3) + (c ^ 48), isdigit(c = getchar()));
return x * f;
}
template inline bool chkmin(T &a,T b) { return a > b ? a = b, 1 : 0; }
template inline bool chkmax(T &a,T b) { return a const int maxN = 5000 + 2;
const int mod = 1e9 + 7;
int n;
int ver[maxN <<1], nxt[maxN <<1], head[maxN + 2];
int dp[maxN + 2][maxN + 2], tmp[maxN + 2], size[maxN + 2], g[maxN + 2];
inline void Inc(int &x) { x <0 ? x += mod : 0; }
inline void Dec(int &x) { x >= mod ? x -= mod : 0; }
void link(int u, int v)
{
static int ecnt = 0;
ver[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt;
}
void dfs(int u, int fa)
{
dp[u][1] = 1;
size[u] = 1;
for (int i = head[u]; i; i = nxt[i])
{
int v = ver[i];
if (v == fa) continue;
dfs(v, u);
for (int i = 0; i <= size[u]; ++i)
for (int j = 0; j <= size[v]; ++j)
Dec(tmp[i + j] += 1ll * dp[u][i] * dp[v][j] % mod);
size[u] += size[v];
for (int i = 0; i <= size[u]; ++i) dp[u][i] = tmp[i], tmp[i] = 0;
}
for (int i = 1; i <= size[u]; ++i) Inc(dp[u][0] -= 1ll * dp[u][i] * g[i] % mod);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("xhc.in", "r", stdin);
freopen("xhc.out", "w", stdout);
#endif
n = read();
for (int i = 1; i {
int u = read(), v = read();
link(u, v), link(v, u);
}
g[0] = 1;
for (int i = 2; i <= n; ++i) g[i] = 1ll * g[i - 2] * (i - 1) % mod;
dfs(1, 0);
printf("%d\n", (mod - dp[1][0]) % mod);
return 0;
}