题目大意
给出一棵树，可以删除其中最多(k)条边，再加上若干条边使得其还是一棵树，问这样的操作能得到多少种不同的树的形态（带编号）。
(nleq 50, 0leq k leq n)
思路
一种升级版的生成树计数。
设树上的边权值为(1)，不存在的边权值为(x)，则构造矩阵(g)：
- 若(i≠j)，则(g[i][j]=)边((i,j))的权值的相反数。
- 若(i=j)，则(g[i][j]=)点(i)相邻边的权值之和。
- 矩阵树定理：构造上述矩阵后，该矩阵其任意一个余子式的行列式(=sum_{所有生成树}边权之积)
- 求行列式的方法：用高斯消元把矩阵消成上三角矩阵后，对角线数字乘积即为其行列式的值。
现在(x)不确定，所以求出来的行列式实际上是一个多项式。这个多项式的(x^k)的系数，就是使用(k)条边权为(x)的边的方案数，即删去原树中(k)条边，再加上(k)条边形成一棵树的方案数。那么问题就变成求这个多项式的系数了。
直接求系数不好做，我们可以考虑先求这个多项式的点值表达，即把(x)分别代换成(n)个不同的数求行列式，然后使用高斯消元或拉格朗日插值法还原系数表达。
最后把(x^0)到(x^k)的系数加起来就是答案了。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=57;
const ll P=998244353;
int n,K;
int a[N][N],f[N];
ll sum,g[N][N][2],b[N][N],y[N],ans[N];
ll mtp[N],tmp[N],mtp1[N];
ll pow(ll a,ll b){
ll ret=1;
for(;b;a=a*a%P,b>>=1)if(b&1)ret=ret*a%P;
return ret;
}
ll inv(ll x){return pow(x%P,P-2);}
ll solve(){
for(int i=1;i<n;++i){
for(int j=i+1;j<n;++j){
ll res=b[j][i]*inv(b[i][i])%P;
for(int k=1;k<n;++k)b[j][k]=(b[j][k]-res*b[i][k]%P+P)%P;
}
}
ll ret=1;
for(int i=1;i<n;++i)ret=ret*b[i][i]%P;
return ret;
}
void domtp(){
memset(tmp,0,sizeof(tmp));
for(int i=0;i<n;++i)for(int j=0;j<2;++j)tmp[i+j]=(tmp[i+j]+mtp[i]*mtp1[j]%P)%P;
memcpy(mtp,tmp,sizeof(tmp));
}
int main(){
freopen("kaisou.in","r",stdin);
//freopen("kaisou.out","w",stdout);
scanf("%d%d",&n,&K);
for(int i=2;i<=n;++i)scanf("%d",&f[i]),++f[i],a[i][f[i]]=a[f[i]][i]=1;
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)--g[i][j][a[i][j]],++g[i][i][a[i][j]];
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)for(int k=1;k<=n;++k)b[j][k]=((g[j][k][0]+P)*i+(g[j][k][1]+P)%P)%P;
y[i]=solve();
}
for(int i=1;i<=n;++i){
ll pp=1;
memset(mtp,0,sizeof(mtp));
mtp[0]=1;
for(int j=1;j<=n;++j)if(j!=i){
mtp1[1]=1,mtp1[0]=P-j;
domtp();
pp=pp*(i-j+P)%P;
}
for(int j=0;j<n;++j)ans[j]=(ans[j]+mtp[j]*inv(pp)%P*y[i]%P)%P;
}
for(int i=0;i<=K;++i)sum=(sum+ans[i])%P;
printf("%lld
",sum);
return 0;
}