陕西省建设建设监理协会网站,丽水专业的网站建设,网站开发软件网站开发,怎么样做淘宝联盟网站传送门 CayleyCayleyCayley公式#xff1a;一个完全图有nn−2n^{n-2}nn−2棵无根生成树#xff08;可用prufer序列证明#xff09; 扩展CayleyCayleyCayley公式#xff1a;被确定边分为大小为a1,a2,⋯,ama_1,a_2,\cdots, a_ma1,a2,⋯,am的连通块#xff0c;则有nm−…传送门
CayleyCayleyCayley公式一个完全图有nn−2n^{n-2}nn−2棵无根生成树可用prufer序列证明 扩展CayleyCayleyCayley公式被确定边分为大小为a1,a2,⋯,ama_1,a_2,\cdots, a_ma1,a2,⋯,am的连通块则有nm−2∏i1main^{m-2}\prod\limits_{i1}^{m}{a_i}nm−2i1∏mai种生成树
我们强制生成树中的一些边与原树中的边相同求出生成树中至少有xxx条边于原树中边相同的方案数ansxans_xansx再容斥得到生成树中恰好有xxx条边与原树中边相同的方案数AnsxAns_xAnsx。
Ansx∑ix(−1)i−x(ix)ansiAns_x\sum\limits_{ix}(-1)^{i-x}\dbinom{i}{x}ans_iAnsxix∑(−1)i−x(xi)ansi
考虑一棵以uuu为根的生成子树里面有jjj条边强制与原树中边相同。如果只加入强制相同的jjj条边我们会得到若干连通块即子树被非强制相同的边分成若干连通块可以用拓展CayleyCayleyCayley公式统计方案数。
nm−2n^{m-2}nm−2可以留到最后处理所以我们只考虑求∏i1mai\prod\limits_{i1}^{m}{a_i}i1∏mai其组合意义为每个连通块内各选一个关键点的方案数。
设dp[u][j][0/1]dp[u][j][0/1]dp[u][j][0/1]表示以uuu为根的子树内有jjj条强制相同的边uuu所在的连通块选/未选选/未选选/未选关键点 的选关键点方案数之和。转移如下
若u−vu-vu−v是强制相同的边(v∈sonuv\in son_uv∈sonu) dp[u][j][0]×dp[v][k][0]→dp[u][jk1][0]dp[u][j][0]\times dp[v][k][0]\to dp[u][jk1][0]dp[u][j][0]×dp[v][k][0]→dp[u][jk1][0] dp[u][j][0]×dp[v][k][1]dp[u][j][1]×dp[v][k][0]→dp[u][jk1][1]dp[u][j][0]\times dp[v][k][1]dp[u][j][1]\times dp[v][k][0]\to dp[u][jk1][1]dp[u][j][0]×dp[v][k][1]dp[u][j][1]×dp[v][k][0]→dp[u][jk1][1] 若u−vu-vu−v是非强制相同的边(v∈sonuv\in son_uv∈sonu) dp[u][j][0]×dp[v][k][1]→dp[u][jk][0]dp[u][j][0]\times dp[v][k][1]\to dp[u][jk][0]dp[u][j][0]×dp[v][k][1]→dp[u][jk][0] dp[u][j][1]×dp[v][k][1]→dp[u][jk][1]dp[u][j][1]\times dp[v][k][1]\to dp[u][jk][1]dp[u][j][1]×dp[v][k][1]→dp[u][jk][1]
类似题目WC2019数树
#includebits/stdc.h
using namespace std;
const int mod1000000007;
const int N8010;
int read(){int x0,f1;char chgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){xx*10ch-0;chgetchar();}return x*f;
}
int add(int x,int y){return xymod?xy-mod:xy;}
int dec(int x,int y){return x-y0?x-ymod:x-y;}
int mul(int x,int y){return 1ll*x*y%mod;}
void Add(int x,int y){xxymod?xy-mod:xy;}
void Dec(int x,int y){xx-y0?x-ymod:x-y;}
void Mul(int x,int y){x1ll*x*y%mod;}
int ksm(int a,int b){if(b0) return ksm(ksm(a,-b),mod-2);int ans1;while(b){if(b1) ansmul(ans,a);amul(a,a);b1;}return ans;
}
int n,fac[N],ifac[N];
int cnt,head[N],nxt[N1],to[N1],siz[N];
vectorintf[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(vectorint v){vectorint().swap(v);
}
void dfs(int u,int fa){siz[u]1;f[u].push_back(1);g[u].push_back(1);for(int ihead[u];i;inxt[i]){int vto[i];if(vfa) continue;dfs(v,u);f[u].resize(siz[u]siz[v]);g[u].resize(siz[u]siz[v]);for(int jsiz[u]-1;j0;j--){const int fuf[u][j],gug[u][j];f[u][j]g[u][j]0;for(int ksiz[v]-1;k0;k--){const int fvf[v][k],gvg[v][k];Add(f[u][jk1],mul(fu,fv));Add(f[u][jk],mul(fu,gv));Add(g[u][jk1],add(mul(fu,gv),mul(gu,fv)));Add(g[u][jk],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(){nread();for(int i1;in;i){int uread(),vread();adde(u,v),adde(v,u);}dfs(1,0);fac[0]1;for(int i1;in;i) fac[i]mul(fac[i-1],i);ifac[n]ksm(fac[n],mod-2);for(int in;i1;i--) ifac[i-1]mul(ifac[i],i);for(int i0;in;i) Mul(g[1][i],ksm(n,n-i-2));for(int i0;in;i){int ans0;for(int ji;jn;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;
}
