ARC101E
Miraik
·
·
题解
先考虑一个 O(n^3) 的简单做法：
设 f_{u,i} 表示 u 的子树内还有 i 个点要向上匹配的方案数。我们发现如果 (u,v) 这条边要被覆盖到，那么 v 的子树内必然有点要向上匹配。
因此合并转移的时候枚举 u 子树内的点数 i，v 子树内的点数 j（注意 j\ge1），以及匹配的对数 k，有转移：
f_{u,i} \times f_{v,j} \times {i \choose k} \times {j \choose k} \times k! \to newf_{u,i+j-2k}
答案即为 f_{1,0}。但是这样做系数很复杂，感觉完全没有优化的空间。
正难则反，考虑容斥求不合法方案。
对于不合法方案，我们可以看作断开一个边集 S，然后给每个联通块内两两配对，得到方案数 T(S)，对答案的贡献即为 (-1)^k \times T(S)。
容易发现的是，大小为 2t 的联通块两两配对，方案数 g(t)=\prod_{i=1}^{t} (2i-1)（注意并不一定是联通的，只是没钦定它们之间被断）
重新设状态 f_{u,i} 表示在 u 子树内，u 所在联通块大小为 i 的方案数。
考虑边的钦定情况，有转移方程：
$f_{u,i} \times f_{v,j} \to newf_{u,i+j} $ 该边没被断
答案为 $ \sum_{i=1}^n f_{1,i} \times g(i)$。时间复杂度 $O(n^2)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
const int mod=1000000007;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
int n,siz[N],g[N],f[N][N],ff[N],ans;
struct Edge{
int to,nxt;
}e[N<<1];
int head[N],tot;
inline void add(int u,int v){
e[++tot]={v,head[u]};
head[u]=tot;
}
inline void dfs(int u,int fa){
siz[u]=1; f[u][1]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
for(int j=1;j<=siz[u];j++) ff[j]=f[u][j],f[u][j]=0;
for(int j=1;j<=siz[u];j++)
for(int k=1;k<=siz[v];k++){
(f[u][j]+=mod-1ll*ff[j]*f[v][k]%mod*g[k]%mod)%=mod;
(f[u][j+k]+=1ll*ff[j]*f[v][k]%mod)%=mod;
}
siz[u]+=siz[v];
}
}
int main(){
n=read();
g[0]=1; for(int i=2;i<=n;i+=2) g[i]=1ll*g[i-2]*(i-1)%mod;
for(int i=1;i<n;i++){
int u=read(),v=read();
add(u,v); add(v,u);
}
dfs(1,-1);
for(int i=1;i<=n;i++) (ans+=1ll*f[1][i]*g[i]%mod)%=mod;
printf("%d\n",ans);
return
```