[ARC101E]Ribbons on Tree

题意：一棵$n$个点的树（$n$是偶数），把所有点分成$\frac n2$对，每对点都在树上路径涂色，问有多少种配对方式使得所有边都被涂上颜色

考虑容斥，设$E$是整棵树的边集，$F\subseteq E$，定义$f(F)$表示有多少种配对满足$F$中的边都不被涂色，那么答案是$\sum\limits_{F\subseteq E}(-1)^{|F|}f(F)$

对于一个给定的$F$，我们容易计算$f(F)$：设删去$F$中边后形成的$|F|+1$个连通块的大小为$n_{1\cdots|F|+1}$，那么$f(F)=\prod\limits_{i=1}^{|F|+1}g(n_i)$，其中$g(n)=[2|n](n-1)!!$

现在我们要求所有的$f(F)$，考虑DP

设$f_{i,j,k}$表示在$i$的子树中，删边数奇偶性为$k$，$i$所在连通块大小为$j$的配对方案数，注意这里的方案数是不管$i$所在连通块是如何配对的，即答案为$\sum\limits_{i=1}^n(f_{root,i,0}-f_{root,i,1})g_i$

转移就很自然了，枚举子树，按当前边删不删进行转移，时间复杂度$O(n^2)$

#include<stdio.h>#include<string.h>typedef long long ll;const int mod=1000000007;int mul(int a,int b){return(ll)a*b%mod;}int ad(int a,int b){return(a+b)%mod;}void inc(int&a,int b){(a+=b)%=mod;}int h[5010],nex[10010],to[10010],M;void add(int a,int b){M++;to[M]=b;nex[M]=h[a];h[a]=M;}int siz[5010],f[5010][5010][2],g[5010],p[5010][2];void dfs(int fa,int x){int i,j,k,t1,t2;siz[x]=1;f[x][1][0]=1;for(i=h[x];i;i=nex[i]){if(to[i]!=fa){dfs(x,to[i]);memset(p,0,sizeof(p));for(j=1;j<=siz[x];j++){for(k=1;k<=siz[to[i]];k++){t1=ad(mul(f[x][j][0],f[to[i]][k][0]),mul(f[x][j][1],f[to[i]][k][1]));t2=ad(mul(f[x][j][0],f[to[i]][k][1]),mul(f[x][j][1],f[to[i]][k][0]));//connectinc(p[j+k][0],t1);inc(p[j+k][1],t2);//removeinc(p[j][0],mul(g[k],t2));inc(p[j][1],mul(g[k],t1));}}siz[x]+=siz[to[i]];memcpy(f[x],p,sizeof(p));}}}int main(){int n,i,x,y,s;scanf("%d",&n);for(i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}g[0]=1;for(i=2;i<=n;i+=2)g[i]=mul(g[i-2],i-1);dfs(0,1);s=0;for(i=2;i<=n;i+=2)inc(s,mul(g[i],f[1][i][0]-f[1][i][1]));printf("%d",ad(s,mod));}