题意与数据范围

给定 \(n\) 个点的树，你需要把这些点分成 \(\frac{n}{2}\) 组，每组恰好 \(2\) 个点，且每个点在至多一组中。

称一个分组方案是好的，当且仅当：如果我们把每对点的最短路上的边都打上标记，最后每条边都被标记了。

求好的分组方案数。答案对 \(10^9+7\) 取模。

\(2\le n\le 5000\)，\(n\) 是偶数。

Solution

设 \(A_i\) 表示第 \(i\) 条边未被覆盖的选择方案的集合，\(S\) 为全集

那么答案即为 \(|\bigcap\limits_{i=1}^{n}\overline{A_i}|=|S|+\sum \limits_{S\in [n]}(-1)^{|S|}\times |\bigcap\limits_{i\in S}A_i|\)

考虑如何求 \(|\bigcap\limits_{i\in S}A_i|\)

显然可以直接枚举 \(S\) 删边然后将每个连通块的 \((x-1)!!\) 相乘，其中 \(x\) 表示连通块大小，为偶数

但是复杂度非常 \(\text{sb}\)

考虑转换一下答案式的形式：

\(|\bigcap\limits_{i=1}^{n}\overline{A_i}|=|S|+\sum\limits_{i=1}^{n-1}(-1)^i(\sum\limits_{S\in [n]且|S|=i}|\bigcap\limits_{i\in S}A_i|)\)

也就是说，对于每一个未被覆盖的边数 \(i\)，我们需要知道一共有多少种方案，然后就可以直接容斥了

设 \(dp_{i,j}\) 表示在以i为根的子树中，有 \(j\) 条边未被覆盖的方案数是多少

然后发现这样没法转移，因为必须要知道割出去的连通块的大小

所以加一维，用 \(dp_{i,j,k}\) 表示答案

但是状态数又炸了

观察答案式，发现我们并不需要知道他究竟未覆盖几条边，因为容斥系数只和奇偶性有关，所以只需要知道其奇偶性就可以了

所以状态优化为 \(dp_{i,j,0/1}\) 表示在以i为根的子树中，它所在的连通块大小为 \(j\)，未覆盖的边数为奇数还是偶数的方案数

于是对于节点i的每一个子节点 \(v\)，有：

\(dp_{i,a+b,c\oplus d}+=dp_{i,a,c}\times dp_{v,b,d}\)

\(dp_{i,a,c\oplus d\oplus 1}+=dp_{i,a,c}\times dp_{v,b,d}\times (b-1)!!\times [b\& 1==0]\)

其中 \(\oplus\) 表示异或运算

初始状态大概就是 \(dp_{i,1,0}=1\)

树形 \(\text{dp}\) 后容斥一下就没了

复杂度 \(O(n^2)\)

代码如下：

#include<cstdio>#include<iostream>using namespace std;const int N=5e3+10;const int mod=1e9+7;int n,A,B,head[N],cnt,dp[N][N][2],f[N][2],son[N],ans,facc[N];struct edge{int nxt,to;}ed[N<<1];inline void addedge(int x,int y){ed[++cnt].to=y;ed[cnt].nxt=head[x];head[x]=cnt;ed[++cnt].to=x;ed[cnt].nxt=head[y];head[y]=cnt;}inline void Add(int &x,int y){x+=y;x-=x>=mod? mod:0;}inline int MOD(int x){x-=x>=mod? mod:0;return x;}inline int Minus(int x){x+=x<0? mod:0;return x;}inline void DFS(int u,int fa){dp[u][1][0]=1;son[u]=1;for(register int i=head[u];i;i=ed[i].nxt){int v=ed[i].to;if(v==fa)continue;DFS(v,u);for(register int j=1;j<=son[u];j++)f[j][0]=dp[u][j][0],dp[u][j][0]=0,f[j][1]=dp[u][j][1],dp[u][j][1]=0;for(register int j=1;j<=son[u];j++)for(register int k=1;k<=son[v];k++){Add(dp[u][j+k][0],MOD(1ll*f[j][0]*dp[v][k][0]%mod+1ll*f[j][1]*dp[v][k][1]%mod));Add(dp[u][j+k][1],MOD(1ll*f[j][0]*dp[v][k][1]%mod+1ll*f[j][1]*dp[v][k][0]%mod));Add(dp[u][j][0],MOD(1ll*f[j][0]*facc[k-1]%mod*dp[v][k][1]%mod+1ll*f[j][1]*facc[k-1]%mod*dp[v][k][0]%mod));Add(dp[u][j][1],MOD(1ll*f[j][1]*facc[k-1]%mod*dp[v][k][1]%mod+1ll*f[j][0]*facc[k-1]%mod*dp[v][k][0]%mod));}son[u]+=son[v];}}int main(){scanf("%d",&n);for(register int i=1;i<n;i++)scanf("%d%d",&A,&B),addedge(A,B);facc[1]=1;for(register int i=3;i<=n;i+=2)facc[i]=1ll*facc[i-2]*i%mod;DFS(1,0);//直接容斥即可，全集会在i==n时加上 for(register int i=2;i<=n;i+=2){Add(ans,1ll*dp[1][i][0]*facc[i-1]%mod);ans=Minus(ans-1ll*dp[1][i][1]*facc[i-1]%mod);}printf("%d\n",ans);return 0;}