[DP记录]AT4352 [ARC101C] Ribbons on Tree

command_block · 2021-02-13 12:46:16 · 个人记录

题意 : 给定一棵 n 个节点的树，保证 n 为偶数。

给树上的点两两配对，对于一对 (u,v)，在树上将 u\leftrightarrow v 的路径染色。

定义一个配对方案合法当且仅当所有边都有颜色。求合法配对方案数，答案对 10^9+7 取模。

转移 : f'[u][k]=\sum\limits_{i=1}\sum\limits_{k_1+k_2=k+2i,k_1\geq i,k_2\geq i}f[u][k_1]f[v][k_2]i!

复杂度为 O(n^3)。

以上 \rm DP 难以优化，改而考虑容斥。

钦定边集 S 不能被覆盖，设方案数为 c ，则贡献为 c(-1)^{|S|}。

考虑钦定边集 S 后如何计算 c 。将不能被覆盖的边断掉，每个连通块内都能任意匹配，对于一个大小为 n 的联通块，方案数即为 W(n)=1\times 3\times 5\dots\times (n-1) ，若 n 为奇数方案为 0。

于是，记 f[u][k] 表示 u 子树内断边之后 u 所在的联通块大小为 k 的贡献总和。

记 g[u] 为 u 子树内的方案数。

边界 : f[u][1]=1

转移 : f'[u][k]=-g[v]f[u][k]+\sum\limits_{k_1+k_2=k}f[u][k_1]f[v][k_2]

其中， -g[v]f[u][k] 是断边的贡献，后者是不断边的贡献。

最终答案即为 g[1]。

根据树形背包，复杂度为 O(n^2)。

#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back 
#define MaxN 5050
using namespace std;
const int mod=1000000007;
vector<int> g[MaxN];
int ans,f[MaxN][MaxN],t[MaxN],s[MaxN],w[MaxN],siz[MaxN];
void dfs(int u)
{
  siz[u]=1;f[u][1]=1;
  for (int i=0,v;i<g[u].size();i++)
    if (!siz[v=g[u][i]]){
      dfs(v);
      for (int k1=1;k1<=siz[u];k1++)
        for (int k2=1;k2<=siz[v];k2++)
          s[k1+k2]=(s[k1+k2]+1ll*f[u][k1]*f[v][k2])%mod;
      siz[u]+=siz[v];
      for (int k=1;k<=siz[u];k++)
        {f[u][k]=(s[k]-1ll*f[u][k]*t[v])%mod;s[k]=0;}
    }
  for (int k=1;k<=siz[u];k++)
    t[u]=(t[u]+1ll*f[u][k]*w[k])%mod;
}
int n;
int main()
{
  scanf("%d",&n);
  w[2]=1;
  for (int i=4;i<=n;i+=2)
    w[i]=1ll*w[i-2]*(i-1)%mod;
  for (int i=1,u,v;i<n;i++){
    scanf("%d%d",&u,&v);
    g[u].pb(v);g[v].pb(u);
  }dfs(1);
  printf("%d",(t[1]+mod)%mod);
  return 0;
}