[DP记录]AT4352 [ARC101C] Ribbons on Tree
command_block
2021-02-13 12:46:16
**题意** : 给定一棵 $n$ 个节点的树，保证 $n$ 为**偶数**。
给树上的点两两配对，对于一对 $(u,v)$，在树上将 $u\leftrightarrow v$ 的路径染色。
定义一个配对方案合法当且仅当所有边都有颜色。求合法配对方案数，答案对 $10^9+7$ 取模。
$n\leq 5000$ ，时限$\texttt{2s}$。
------------
不难想到如下 $\rm DP$ :
$f[u][k]$ 表示 $u$ 子树内剩余 $k$ 个节点没有匹配，且匹配路径以及未匹配点到 $u$ 的路径覆盖整个子树的方案数。
边界 : $f[u][0]=1$
转移 : $f'[u][k]=\sum\limits_{i=1}\sum\limits_{k_1+k_2=k+2i,k_1\geq i,k_2\geq i}f[u][k_1]f[v][k_2]i!$
复杂度为 $O(n^3)$。
以上 $\rm DP$ 难以优化，改而考虑容斥。
钦定边集 $S$ 不能被覆盖，设方案数为 $c$ ，则贡献为 $c(-1)^{|S|}$。
考虑钦定边集 $S$ 后如何计算 $c$ 。将不能被覆盖的边断掉，每个连通块内都能任意匹配，对于一个大小为 $n$ 的联通块，方案数即为 $W(n)=1\times 3\times 5\dots\times (n-1)$ ，若 $n$ 为奇数方案为 $0$。
于是，记 $f[u][k]$ 表示 $u$ 子树内断边之后 $u$ 所在的联通块大小为 $k$ 的贡献总和。
记 $g[u]$ 为 $u$ 子树内的方案数。
边界 : $f[u][1]=1$
转移 : $f'[u][k]=-g[v]f[u][k]+\sum\limits_{k_1+k_2=k}f[u][k_1]f[v][k_2]$
其中， $-g[v]f[u][k]$ 是断边的贡献，后者是不断边的贡献。
$g[u]=\sum\limits_{k=1}f[u][k]\cdot W(k)$
最终答案即为 $g[1]$。
根据树形背包，复杂度为 $O(n^2)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define MaxN 5050
using namespace std;
const int mod=1000000007;
vector<int> g[MaxN];
int ans,f[MaxN][MaxN],t[MaxN],s[MaxN],w[MaxN],siz[MaxN];
void dfs(int u)
{
siz[u]=1;f[u][1]=1;
for (int i=0,v;i<g[u].size();i++)
if (!siz[v=g[u][i]]){
dfs(v);
for (int k1=1;k1<=siz[u];k1++)
for (int k2=1;k2<=siz[v];k2++)
s[k1+k2]=(s[k1+k2]+1ll*f[u][k1]*f[v][k2])%mod;
siz[u]+=siz[v];
for (int k=1;k<=siz[u];k++)
{f[u][k]=(s[k]-1ll*f[u][k]*t[v])%mod;s[k]=0;}
}
for (int k=1;k<=siz[u];k++)
t[u]=(t[u]+1ll*f[u][k]*w[k])%mod;
}
int n;
int main()
{
scanf("%d",&n);
w[2]=1;
for (int i=4;i<=n;i+=2)
w[i]=1ll*w[i-2]*(i-1)%mod;
for (int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].pb(v);g[v].pb(u);
}dfs(1);
printf("%d",(t[1]+mod)%mod);
return 0;
}
```