傳送門

$Cayley$公式：一個完全圖有$n^{n?2}$棵無根生成樹（可用prufer序列證明）
擴展$Cayley$公式：被確定邊分為大小為$a_1,a_2,?,a_m$的連通塊，則有$n^{m?2}\prod _{i=1}^m{a}_i$種生成樹

我們強制生成樹中的一些邊與原樹中的邊相同，求出生成樹中至少有$x$條邊于原樹中邊相同的方案數$an{s}_x$，再容斥得到生成樹中恰好有$x$條邊與原樹中邊相同的方案數$An{s}_x$。

$An{s}_x=\sum _{i=x}(?1{)}^{i?x}(\genfrac{}{}{0ex}{}{i}{x})an{s}_i$

考慮一棵以$u$為根的生成子樹，里面有$j$條邊強制與原樹中邊相同。如果只加入強制相同的$j$條邊，我們會得到若干連通塊，即子樹被非強制相同的邊分成若干連通塊，可以用拓展$Cayley$公式統計方案數。

$n^{m?2}$可以留到最后處理，所以我們只考慮求$\prod _{i=1}^m{a}_i$，其組合意義為每個連通塊內各選一個關鍵點的方案數。

設$dp[u][j][0/1]$表示以$u$為根的子樹內有$j$條強制相同的邊，$u$所在的連通塊$選/未選$關鍵點 的選關鍵點方案數之和。轉移如下：

若$u?v$是強制相同的邊($v\in so{n}_u$)：
$dp[u][j][0]\times dp[v][k][0]\to dp[u][j+k+1][0]$
$dp[u][j][0]\times dp[v][k][1]+dp[u][j][1]\times dp[v][k][0]\to dp[u][j+k+1][1]$
若$u?v$是非強制相同的邊($v\in so{n}_u$)：
$dp[u][j][0]\times dp[v][k][1]\to dp[u][j+k][0]$
$dp[u][j][1]\times dp[v][k][1]\to dp[u][j+k][1]$

類似題目：WC2019數樹

#include<bits/stdc++.h> using namespace std; const int mod=1000000007; const int N=8010; int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int add(int x,int y){return x+y>=mod?x+y-mod:x+y;} int dec(int x,int y){return x-y<0?x-y+mod:x-y;} int mul(int x,int y){return 1ll*x*y%mod;} void Add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;} void Dec(int &x,int y){x=x-y<0?x-y+mod:x-y;} void Mul(int &x,int y){x=1ll*x*y%mod;} int ksm(int a,int b){if(b<0) return ksm(ksm(a,-b),mod-2);int ans=1;while(b){if(b&1) ans=mul(ans,a);a=mul(a,a);b>>=1;}return ans; } int n,fac[N],ifac[N]; int cnt,head[N],nxt[N<<1],to[N<<1],siz[N]; vector<int>f[N],g[N];//f:0,g:1 void adde(int u,int v){to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt; } void Clear(vector<int> &v){vector<int>().swap(v); } void dfs(int u,int fa){siz[u]=1;f[u].push_back(1);g[u].push_back(1);for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v==fa) continue;dfs(v,u);f[u].resize(siz[u]+siz[v]);g[u].resize(siz[u]+siz[v]);for(int j=siz[u]-1;j>=0;j--){const int fu=f[u][j],gu=g[u][j];f[u][j]=g[u][j]=0;for(int k=siz[v]-1;k>=0;k--){const int fv=f[v][k],gv=g[v][k];Add(f[u][j+k+1],mul(fu,fv));Add(f[u][j+k],mul(fu,gv));Add(g[u][j+k+1],add(mul(fu,gv),mul(gu,fv)));Add(g[u][j+k],mul(gu,gv));}}siz[u]+=siz[v];Clear(f[v]),Clear(g[v]);} } int C(int n,int m){return mul(mul(fac[n],ifac[m]),ifac[n-m]); } int main(){n=read();for(int i=1;i<n;i++){int u=read(),v=read();adde(u,v),adde(v,u);}dfs(1,0);fac[0]=1;for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);ifac[n]=ksm(fac[n],mod-2);for(int i=n;i>=1;i--) ifac[i-1]=mul(ifac[i],i);for(int i=0;i<n;i++) Mul(g[1][i],ksm(n,n-i-2));for(int i=0;i<n;i++){int ans=0;for(int j=i;j<n;j++){if((j-i)&1) Dec(ans,mul(C(j,i),g[1][j]));else Add(ans,mul(C(j,i),g[1][j]));}printf("%d ",ans);}return 0; }

總結

以上是生活随笔為你收集整理的[XXSY] 构树（prufer序列，树上连通块DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。