[ARC101C] Ribbons on Tree （容斥+DP）
AT4352 [ARC101C] Ribbons on Tree
妙题，如果按照套路子树 DP 匹配子树内外的点 \(O(n^3)\)
但是剑走偏锋容斥一下，钦定若干条边一定不被覆盖，发现问题变成了若干个联通块任意配对方案数乘积
而一个大小为 \(n\) （\(n\) 为偶数）联通块任意匹配方案数为
\[g_n=\prod_{i=1}^{\frac{n}{2}} (2i-1) \]考虑用 DP 优化容斥，转移过程中维护容斥系数，\(f_{u,i}\) 表示 \(u\) 目前所在联通块大小为 \(i\) ，暴力卷起来转移即可
#include
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin)),p1==p2?EOF:*p1++)
#pragma GCC optimize(2,3,"Ofast")
using namespace std;
char buf[1<<22],*p1=buf,*p2=buf;
int read(){
char c=getchar();int x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
const int _=5003;
const int P=1000000007;
int hd[_],ver[_<<1],nxt[_<<1],tot;
void add(int u,int v){nxt[++tot]=hd[u];hd[u]=tot;ver[tot]=v;}
int f[_][_],g[_],sz[_],t[_],n;
void dfs(int u,int fa){
sz[u]=1;f[u][1]=1;
for(int i=hd[u],v;i;i=nxt[i])
if((v=ver[i])^fa){
dfs(v,u);
for(int j=0;j<=sz[u];++j) t[j]=f[u][j],f[u][j]=0;
for(int j=1;j<=sz[u];++j)
for(int k=0;k<=sz[v];++k)
f[u][j+k]=(f[u][j+k]+1ll*t[j]*f[v][k])%P;
sz[u]+=sz[v];
}
for(int i=2;i<=sz[u];i+=2)
f[u][0]=(f[u][0]-1ll*g[i]*f[u][i]%P+P)%P;
}
int main(){
n=read();
for(int i=1;i