题面
思路
果然ATcoder上的都是代码难度小的思维题啊。
这题是一道奇妙的树形背包dp。首先可以考虑容斥，枚举每一条边是否有颜色，有颜色的点构成若干连通块，然后块内点就可以自由配对。易知n为奇数时方案数(p[n]=0)，偶数时(p[n]=(n-1)*(n-3)*…3*1)。但这样复杂度显然爆炸。
于是考虑在dp过程中带上容斥系数转移。可令(f[i][j])表示dp到以(i)为根的子树，子树内与(i)的父亲在同一个连通块内的有(j)个点。一般情况就像背包一样转移即可。而(f[i][0])就代表(i)与父亲不连通。即(i)到父亲的边没有颜色，所以要乘上一个容斥系数(-1)。所以转移方程为(f[i][0]=-Sigma_{j=1}^nf[i][j]*p[j])。但根节点时因为不存在与父亲的边，所以不用乘-1。
我一开始理解的(f[i][j])是j表示i子树中有多少点还未配对，但这样是不准确的，因为点的配对是在最后确定i与父亲不连通时统一计数的。这种状态设计虽然简单，但无法不重不漏的考虑。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define ri register int
using namespace std;
int read(){
int res=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
res=(res<<1)+(res<<3)+ch-'0';
ch=getchar();
}
return res*f;
}
const int N=5e3+5,inf=1e9+7;
struct qq{
int next,to;
}a[N<<1];
int head[N],siz[N],f[N][N],g[N],pre[N],num;
void add(int x,int y){
a[++num].next=head[x];
head[x]=num;
a[num].to=y;
}
void updata(int &x){
if(x>=inf) x-=inf;
if(x<0) x+=inf;
return ;
}
void dfs(int p,int fa){
siz[p]=f[p][1]=1;
for(int i=head[p];i;i=a[i].next){
if(a[i].to!=fa){
dfs(a[i].to,p);
for(int j=1;j<=siz[p]+siz[a[i].to];j++) g[j]=0;
for(int j=1;j<=siz[p];j++){
for(int k=0;k<=siz[a[i].to];k++){
g[j+k]+=1ll*f[p][j]*f[a[i].to][k]%inf;
updata(g[j+k]);
}
}
for(int j=1;j<=siz[p]+siz[a[i].to];j++) f[p][j]=g[j];
siz[p]+=siz[a[i].to];
}
}
for(int i=1;i<=siz[p];i++) f[p][0]-=1ll*f[p][i]*pre[i]%inf,updata(f[p][0]);
}
int main(){
int i,j,k,l,n,m;
// freopen();
// freopen();
n=read();
for(i=1;i<n;i++){
k=read();l=read();
add(k,l);add(l,k);
}
pre[0]=1;
for(i=2;i<=n;i+=2)
pre[i]=1ll*pre[i-2]*(i-1)%inf;
dfs(1,0);
printf("%d",inf-f[1][0]);
return 0;
}