Description
Solution
- 神仙计数题。
- 考虑树形DP。
- 为了DP的方便，有一种很骚的操作，因为是对于每一个恰好为c个好点的状态求，我们为了复杂度不好记录c。
- 但是我们可以将它转化为至少c个好点。
- 考虑对于每一个合法的好点的选择方案，枚举它的子集，每一个子集的贡献就只用当作，只用我们将k变成k-1，将它当作每多一个好点的贡献进行转移就好了。
- 设表示x的子树内，以1~size[x]给它们编号之后，最小的好点的编号为j。
- 合并的时候类似树形依赖背包，枚举当前size和儿子的size，将它们合并在一起。具体来说就是讨论哪一个里面的最小的好点合并后是最小的，并考虑小于它的点有多少个以及插入的方案数。
- 注意并不是儿子里面都一定有好点，有可能儿子里没有好点，因为状态没有记录这个东西，所以要单独计算。
- 最好考虑当前的根是否是好点，对于f[x][i]首先要插在i前面，如果是好点的话要求一个后缀和，当然也要特殊计算儿子里面没有好点，当前根单独一个好点的情况。
- 最后要考虑整棵树都没有好点的贡献。
- 具体细节很多。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 5005
#define ll long long
#define mo 998244353
using namespace std;
int n,i,j,k,x,y;
int em,e[maxn*2],nx[maxn*2],ls[maxn];
ll ans,K,Kp,C[maxn][maxn],fct[maxn];
void insert(int x,int y){
em++; e[em]=y; nx[em]=ls[x]; ls[x]=em;
em++; e[em]=x; nx[em]=ls[y]; ls[y]=em;
}
int sz[maxn],p,q; ll f[maxn][maxn],g[maxn],s0[maxn],s1[maxn];
void dp(int x,int y){
for(j=0;j<=sz[x];j++) g[j]=f[x][j];
s0[sz[x]+1]=fct[sz[x]];
for(j=sz[x];j>=1;j--) s0[j]=(s0[j+1]+f[x][j])%mo;
s1[sz[y]+1]=fct[sz[y]];
for(j=sz[y];j>=1;j--) s1[j]=(s1[j+1]+f[y][j])%mo;
for(j=0;j<=sz[x]+sz[y];j++) f[x][j]=0;
for(p=1;p<=sz[x];p++) for(k=0;k<=sz[y];k++)
f[x][p+k]+=C[p+k-1][p-1]*C[sz[x]+sz[y]-p-k][sz[x]-p]%mo*g[p]%mo*s1[k+1]%mo;
for(q=1;q<=sz[y];q++) for(k=0;k<=sz[x];k++)
f[x][q+k]+=C[q+k-1][q-1]*C[sz[x]+sz[y]-q-k][sz[y]-q]%mo*f[y][q]%mo*s0[k+1]%mo;
sz[x]+=sz[y];
for(j=1;j<=sz[x];j++) f[x][j]%=mo;
}
void dfs(int x,int p){
for(int i=ls[x];i;i=nx[i]) if (e[i]!=p)
dfs(e[i],x),dp(x,e[i]);
sz[x]++;
ll sum=0;
for(int j=sz[x];j;j--) {
(sum+=f[x][j])%=mo;
f[x][j]=(f[x][j-1]*(j-1)%mo+sum*K%mo+fct[sz[x]-1]*K%mo)%mo;
}
}
int main(){
scanf("%d%lld",&n,&K),K--;
for(i=1;i<n;i++) scanf("%d%d",&x,&y),insert(x,y);
C[0][0]=1,fct[0]=1;
for(i=1;i<=n;i++){
C[i][0]=1,fct[i]=fct[i-1]*i%mo;
for(j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
}
dfs(1,0);
ll ans=fct[n];
for(i=1;i<=n;i++) ans+=f[1][i];
printf("%lld",ans%mo);
}