【容斥原理】【树形DP】Atcoder ARC101 Ribbons on Tree

分析：

很不错的树形DP+容斥原理的混合题

不得不说，尽管Atcoder去世了一个半月，但这次题目质量仍然保持得很不错

首先，这题可以运用容斥原理转化一下：定义$E$为给出的边集，设$F\subseteq E$，$f(F)$表示：F中的边全部未被覆盖的方案数。

答案就是$\sum (-1)^{|F|}f(F)$

那么接下来就是求$f(F)$

其实这个很显然，考虑在树上去除所有F中的边，那么每次选择的点对，都必须在剩下的图中的同一个联通块内。这样的联通块必定有$|F|+1$个，设其点数分别为$n_1,n_2,n_3…n_{|F|+1}$

设一个函数$g(n)$表示在n个点中选出点两两一组的方案数。
那么很显然当n为奇数时，$g(n)=0$
否则$g(n)=(n-1)*(n-3)*……*3*1$

那么$f(F)=g(n_1)*g(n_2)*g(n_3)……g(n_{|F|+1})$

现在考虑快速地求$f(F)$，这时树形DP就派上用场了。

定义$dp(x,sum)$表示以x为根的子树中，和x的父亲相连的点有sum个时的方案数。

转移也就很明显了，依次遍历每个亲儿子，暴力枚举在这个儿子的子树中选$k$个点的方案数。

当sum=0时，就相当于和父亲的边在F中，这种情况的转移比较特殊，因为此时相当于一个联通块被考虑完了，所以要枚举所有可能的联通块大小，并且由于$F$多了这一条边，所以要全部取相反数，$dp(x,0)=-\sum dp(x,sum')*f(sum')$。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 5010
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll dp[MAXN][MAXN],f[MAXN],t[MAXN];
int siz[MAXN];
vector<int> a[MAXN];
void dfs(int x,int fa){siz[x]=1;dp[x][1]=1;for(int i=0;i<a[x].size();i++){int u=a[x][i];if(u==fa)continue;dfs(u,x);for(int j=0;j<=siz[x];j++){t[j]=dp[x][j];dp[x][j]=0;}for(int j=0;j<=siz[x];j++)for(int k=0;k<=siz[u];k++)(dp[x][j+k]+=t[j]*dp[u][k]%MOD)%=MOD;siz[x]+=siz[u];}for(int i=0;i<=siz[x];i+=2)dp[x][0]=(dp[x][0]-dp[x][i]*f[i]%MOD+MOD)%MOD;
}
int n,u,v;
int main(){SF("%d",&n);for(int i=1;i<n;i++){SF("%d%d",&u,&v);a[u].push_back(v);a[v].push_back(u);}   f[0]=1;for(int i=2;i<=n;i+=2)f[i]=f[i-2]*(i-1)%MOD;dfs(1,0);PF("%lld",MOD-dp[1][0]);
}