题目链接

ARC101E - Ribbons on Tree

题解

令边集\(S \subseteq E\) 设\(f(S)\)为边集S中没有边被染色的方案数

容斥一下，那么\(ans = \sum_{S \subseteq E} (-1)^{ \| S\| f(S) }\)

那么如何求对于原边集的\(f(S)\),也就是把\(S\)集合中的边全部删掉之后的各联通块内匹配的乘积

设\(g(x)\)为大小为x的联通块内点两两匹配的方案

那么\(f(S)=\prod_{i=1}^{|S|+1}g(a_i)\)

考虑如何求ans

设\(dp[i][j]\)表示以i为跟的子树中，有j各点没有在子树种匹配(链接到父节点

转移背包一下

对于\(j=0\)的时候由于那么i节点到父亲的边是没有覆盖的，容斥系数要取反

那么

$ f[i][0]=\sum_{j=1}^{sz[i]}-1\times f[i][j]\times g(j) $

代码

#include<cstdio> #include<cstring> #include<algorithm> #define rep(p,x,k) for(int p = x;p <= k;++ p) #define per(p,x,k) for(int p = x;p >= k;-- p) #define gc getchar()#define pc putchar #define LL long long #define int long longinline LL read() {LL x = 0,f = 1; char c = gc; while(c < '0' || c > '9') c = gc; while(c <= '9' && c >= '0') x = x * 10 + c -'0',c = gc; return x ; } void print(LL x) { if(x < 0) { pc('-'); x = -x; } if(x >= 10) print(x / 10); pc(x % 10 + '0'); } const int maxn = 5007; const int mod = 1e9 + 7; int a[maxn]; int n; struct node { int v,next; } edge[maxn << 1]; int num = 0,head[maxn]; inline void add_edge(int u,int v) {edge[++ num].v = v; edge[num].next = head[u];head[u] = num; } int g[maxn]; int dp[maxn][maxn]; int siz[maxn]; void dfs(int x,int fa) { static int t[maxn]; dp[x][1] = 1; siz[x] = 1; for(int i = head[x];i;i = edge[i].next) { int v = edge[i].v; if(v == fa) continue; dfs(v,x); for(int j = 0,kel = siz[v];j <= siz[x];++ j) {for(int k = 0;k <= siz[v];++ k) { (t[j + k] += 1ll * dp[x][j] * dp[v][k] % mod) %= mod; } } siz[x] += siz[v]; for(int j = 0;j <= siz[x];++ j) dp[x][j] = t[j],t[j] = 0; } LL sum = 0; for(int i = 0;i <= siz[x];i += 2) sum += mod - 1ll * dp[x][i] * g[i] % mod;dp[x][0] = sum % mod; } main() { n = read(); int u,v; rep(i, 1,n - 1) { u = read(),v = read(); add_edge(u,v); add_edge(v,u); } g[0] = 1; for(int i = 2;i <= n;i += 2) (g[i] = 1ll * g[i - 2] * (i - 1)) %= mod; dfs(1,1); print((mod - dp[1][0]) % mod); return 0; } /*41 21 31 4 */