ARC101E - Ribbons on Tree 树形DP

题意

在一个有nnn个点的树上，nnn为偶数，把所有的点两两配对，配对点之间的路径染色，求把树上所有路径染色的方案数，对1e9+71e9 + 71e9+7取模

这个题完全想不出来 最后还是RudyGayRudy\ GayRudyGay告诉我才过了啊

设f(F)(F⊆E)f(F) (F⊆E)f(F)(F⊆E)为FFF集合中的所有边都没被覆盖的方案数

那么Ans=∑F⊆E(−1)∣F∣f(F)Ans = \sum\limits{F\subseteq E}(-1)^{|F|}f(F)Ans=∑F⊆E(−1)∣F∣f(F)

对于一个给定的FFF, f(F)f(F)f(F)很好算

因为这∣F∣|F|∣F∣条边把树分成了∣F∣+1|F| + 1∣F∣+1 个联通块

所以 f(F)=∏i=1∣F∣+1g(ni)f(F)=\prod\limits_{i=1}^{|F|+1}g(n_i)f(F)=i=1∏∣F∣+1​g(ni​)

其中g(x)g(x)g(x)表示把xxx个点任意配对的方案数

我们可以对于每个子树来考虑 若子树内都匹配完

相当于其连向父亲的边被要求删除了 就可以用树形dpdpdp来求解了

那么我们可以设f[i][j]f[i][j]f[i][j]表示在iii子树内有jjj个点要与子树外的点匹配的方案数

那么我们暴力枚举子树转移就可以了

时间复杂度Θ(n2)\Theta(n^2)Θ(n2)

这个东西证明的话就是对于任意两个点只会在他们lcalcalca算贡献的时候被枚举一次

然后每两个点的lcalcalca是唯一的，所以总复杂度是O(n2)O(n^2)O(n2)的

特别地， j=0j = 0j=0的时候iii向它父亲的边一定是没有被覆盖的

这个时候因为多了这一条边 容斥系数要乘上−1-1−1

所以f[i][0]=−∑j=1sizeif[i][j]×g[j]f[i][0] = -\sum_{j = 1}^{size_i}f[i][j]×g[j]f[i][0]=−∑j=1sizei​​f[i][j]×g[j]

或者也可以这样考虑 如果这条边没有被覆盖相当于多增加一个联通块

那么联通块内部肯定要匹配完

Codes

#include<bits/stdc++.h>#define pb push_backusing namespace std;const int N = 5000 + 10;const int mod = 1e9 + 7;vector<int> G[N];int f[N][N], g[N], tmp[N];int n, size[N];void dfs(int u, int dad) {f[u][size[u] = 1] = 1;for(auto v : G[u]) if(v != dad) {dfs(v, u);for(int i = 1; i <= size[u] + size[v]; ++ i) tmp[i] = 0;for(int i = 1; i <= size[u]; ++ i)for(int j = 0; j <= size[v]; ++ j)(tmp[i + j] += 1ll * f[u][i] * f[v][j] % mod) %= mod;for(int i = 1; i <= size[u] + size[v]; ++ i)f[u][i] = tmp[i];size[u] += size[v];}for(int i = 2; i <= size[u]; i += 2)(f[u][0] += mod - 1ll * f[u][i] * g[i] % mod) %= mod;}int main() {#ifdef ylsakioifreopen("e.in", "r", stdin);freopen("e.out", "w", stdout);#endifint x, y; g[0] = 1;scanf("%d", &n);for(int i = 2; i <= n; i += 2)g[i] = 1ll * g[i - 2] * (i - 1) % mod;for(int i = 1; i < n; ++ i) {scanf("%d%d", &x, &y);G[x].pb(y), G[y].pb(x);}dfs(1, 0);printf("%d\n", mod - f[1][0]);return 0;}