湖州交通网站集约化建设项目,成都设计公司地址,sem推广软件,酒店网站怎么制作D-Rebuild Tree
Prufer 是这样建立的#xff1a;每次选择一个编号最小的叶结点并删掉它#xff0c;然后在序列中记录下它连接到的那个结点。重复n−2n-2n−2次后就只剩下两个结点#xff0c;算法结束。#xff08;为什么不是n−1n-1n−1次呢#xff1f;因为第n−1n-1n−1…D-Rebuild Tree
Prufer 是这样建立的每次选择一个编号最小的叶结点并删掉它然后在序列中记录下它连接到的那个结点。重复n−2n-2n−2次后就只剩下两个结点算法结束。为什么不是n−1n-1n−1次呢因为第n−1n-1n−1次操作序列记录下的节点一定是nnn 一个 nnn个点 mmm条边的带标号无向图有 kkk个连通块。我们希望添加k−1k-1k−1条边使得整个图连通。方案数为nk−2⋅∏i1ksin^{k-2}·\prod_{i1}^{k}s_ink−2⋅i1∏ksi 证明考虑组合意义详细见 OIWIKIPrufer 序列 有了上面结论删kkk条边之后形成k1k1k1个连通块设每个连通块的大小为sis_isi 则生成树个数为nk−1⋅∏i1k1sin^{k-1}·\prod_{i1}^{k1}s_ink−1⋅∏i1k1si该题就是求∑split(n,k)nk−1⋅∏i1k1sink−1⋅∑split(n,k)∏i1k1si\sum_{\text{split(n,k)}}n^{k-1}·\prod_{i1}^{k1}s_in^{k-1}·\sum_{\text{split(n,k)}}\prod_{i1}^{k1}s_isplit(n,k)∑nk−1⋅i1∏k1sink−1⋅split(n,k)∑i1∏k1si求∑split(n,k)∏i1k1si\sum_{\text{split(n,k)}}\prod_{i1}^{k1}s_i∑split(n,k)∏i1k1si可以考虑将问题转化为等价问题删掉kkk条边且在每个联通块选一个点的方案数由于每个连通块有sis_isi种选择即得出∏i1k1si\prod_{i1}^{k1}s_i∏i1k1si。
设计dp fu,j,0/1f_{u,j,0/1}fu,j,0/1表示uuu子树内删了jjj条边是否选择点的方案数。
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
const int N50010,mod998244353;
int n,m;
vectorint e[N];
ll qmi(ll a,ll b)
{ll v1;while(b){if(b1) vv*a%mod;b1;aa*a%mod;}return v;
}
ll f[N][105][2];
ll g[105][2];
int sz[N];
void dfs(int u,int fa)
{sz[u]1;f[u][0][0]f[u][0][1]1;for(auto v:e[u]){if(vfa) continue;dfs(v,u);memset(g,0,sizeof g);for(int i0;imin(sz[u]-1,m);i)for(int j0;jsz[v]ijm;j){g[ij][0](g[ij][0]f[u][i][0]*f[v][j][0]%mod)%mod;g[ij][1](g[ij][1]f[u][i][0]*f[v][j][1]%modf[u][i][1]*f[v][j][0]%mod)%mod;if(ijm) continue;g[ij1][0](g[ij1][0]f[u][i][0]*f[v][j][1]%mod)%mod;g[ij1][1](g[ij1][1]f[u][i][1]*f[v][j][1]%mod)%mod;}sz[u]sz[v];memcpy(f[u],g,sizeof g);}
}
int main()
{nrd(),mrd();for(int i1;in;i){int urd(),vrd();e[u].push_back(v);e[v].push_back(u);}dfs(1,0);printf(%lld\n,f[1][m][1]*qmi(n,m-1)%mod);}
