D - Rebuild Tree
Description
给出一个\(n(n\leq5\times10^4)\)个点的树，从中删去\(k(k\leq100)\)条边，再任加\(k\)条边，使得其仍是一棵树，求方案数。
Solution
prufer序列+推推推。
删去\(k\)条边之后树就变成了\(k+1\)个连通块，设每块的大小为\(s_i\)。把每一块视为一个大点，则由其构成的树对应一个长度为\((k+1)-2\)的prufer序列。由于两个块\(i,j\)之间连边的方案数是\(s_is_j\)，那么这棵树对应的方案数即为\(\prod s_i^{c_i+1}=\prod s_i^{c_i}\prod s_i\)，其中\(c_i\)为prufer序列中\(i\)的出现次数，即度数-1。在\(\prod s_i^{c_i}\prod s_i\)中，后一项是和prufer序列无关的，那么只需考虑前一项，即求\(t=\sum_{prufer(k-1)}\prod s_i^{c_i}\)，其中\(prufer(n)\)表示一个长度为\(n\)的prufer序列。
当在prufer序列的一个位置上填\(i\)时，会使得\(c_i\)加一，对\(t\)的贡献是\(s_i\)。具体来说：
\[\begin{align} t & = \sum_{prufer(k-1)}\prod s_i^{c_i} \\ & = \sum_{p_1=1}^{k+1}\sum_{prufer(k-2)}\prod s_i^{c_i}s_{p_1} & 注：c_i此时对应prufer(k-2)\\ & = \sum_{p_1=1}^{k+1}s_{p_1}\sum_{prufer(k-2)}\prod s_i^{c_i} \\ & = n\sum_{prufer(k-2)}\prod s_i^{c_i} \\ & = n^k \end{align} \]那么答案即为\(ans=\sum_{split}t\prod s_i=n^k\sum_{split}\prod s_i\)，该\(\sum\)可以转化为：将树删掉\(k\)条边，每块选择一个点的方案数。那么可以用树形DP解决：设\(f(u,i,0/1)\)表示以\(u\)为根的子树被删了\(i\)条边，\(u\)所在的这一块还未/已经选点。
时间复杂度\(O(nk^2)\)，树形DP里面根据子树大小优化一下就能过。
Code
//Rebuild Tree
#include <cstdio>
#include <vector>
using std::vector;
typedef long long lint;
const int N=5e4+10;
const int K=100+10;
const int P=998244353;
lint fpow(lint x,int y) {lint r=1; for(y;y;y>>=1,x=x*x%P) if(y&1) r=r*x%P; return r;}
int n,k; vector<int> e[N];
int siz[N];
lint f[N][K][2]; lint tmp[K][2];
void dp(int u,int fa)
{
siz[u]=1;
f[u][0][0]=1,f[u][0][1]=1;
for(int v:e[u])
{
if(v==fa) continue;
dp(v,u);
for(int i=0;i<siz[u];i++)
for(int j=0;j<siz[v]&&i+j<=k;j++)
{
tmp[i+j][0]=(tmp[i+j][0]+f[u][i][0]*f[v][j][0])%P;
tmp[i+j][1]=(tmp[i+j][1]+f[u][i][1]*f[v][j][0]+f[u][i][0]*f[v][j][1])%P;
tmp[i+j+1][0]=(tmp[i+j+1][0]+f[u][i][0]*f[v][j][1])%P;
tmp[i+j+1][1]=(tmp[i+j+1][1]+f[u][i][1]*f[v][j][1])%P;
}
siz[u]+=siz[v];
for(int i=0;i<siz[u];i++)
{
f[u][i][0]=tmp[i][0],f[u][i][1]=tmp[i][1];
tmp[i][0]=tmp[i][1]=0;
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n-1;i++)
{
int u,v; scanf("%d%d",&u,&v);
e[u].push_back(v),e[v].push_back(u);
}
dp(1,0);
printf("%lld\n",fpow(n,k-1)*f[1][k][1]%P);
return 0;
}