传送门

没想到我退役前还能做到$prufer$序列的题。。。

转换一下，最大度数恰好为$m$的方案数即为最大度数不超过$m$的方案数减去不超过$m-1$的方案数。

无根树？有标号？度数？数数？$prufer$序列！

最大度数不超过$m$的方案数就是值域为$[1,n]\bigcap \mathbb{Z}$、长度为$n-2$、任意元素出现次数不超过$m-1$的序列个数。

如果每个点度数是确定的，其方案数为：$\dfrac{(n-2)!}{\prod\limits_{i=1}^n(d_i-1)!}$。

于是可以构造一个$EGF$：$F(x)=\sum\limits_{i=0}^{m-1}\dfrac{x^i}{i!}$，$i$表示一个点的出现次数。

考虑$F\times F$的意义：一个$\dfrac{x^i}{i!}$和$\dfrac{x^j}{j!}$相乘，对$x^{i+j}$有$\dfrac{1}{i!j!}$的贡献。

这和前面确定度数的式子很吻合。于是答案为$(n-2)![x^{n-2}]F^n(x)$。

多项式快速幂即可。懒得写$\ln$和$\exp$，直接$O(n\log^2n)$暴力好了。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 140005    
#define inf 0x3f3f3f3f

const int mod = 998244353;
const int g = 3;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
inline int quickpow(int x,int y=mod-2){
    int ans=1;
    while(y){
        if(y&1)ans=1ll*ans*x%mod;
        x=1ll*x*x%mod,y>>=1;
    }
    return ans;
}
const int ig = quickpow(g);
int tr[maxn];
inline int qm(int x){return x>=mod?x-mod:x;}
void NTT(int *f,int n,bool t){
    for(register int i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
    for(register int p=2;p<=n;p<<=1){
        int len=p>>1,o=quickpow(t?ig:g,(mod-1)/p);
        for(register int i=0;i<n;i+=p){
            int gen=1,cop;
            for(register int j=i;j<i+len;++j){
                cop=1ll*f[j+len]*gen%mod,gen=1ll*gen*o%mod;
                f[j+len]=qm(f[j]+mod-cop),f[j]=qm(f[j]+cop);
            }
        }
    }
    if(t){
        int inv=quickpow(n);
        for(register int i=0;i<n;++i)f[i]=1ll*f[i]*inv%mod;
    }
}
int F[maxn];
void Pow(int *g,int n,int y){
    int lim=1;
    while(lim<n<<1)lim<<=1;
    for(register int i=0;i<lim;++i)tr[i]=(tr[i>>1]>>1)|(i&1?lim>>1:0);
    NTT(g,lim,0),--y;
    for(register int i=0;i<lim;++i)F[i]=g[i];
    while(y){
        if(y&1){
            for(register int i=0;i<lim;++i)F[i]=1ll*F[i]*g[i]%mod;
            NTT(F,lim,1);
            for(register int i=n;i<lim;++i)F[i]=0;
            NTT(F,lim,0);
        }
        for(register int i=0;i<lim;++i)g[i]=1ll*g[i]*g[i]%mod;
        NTT(g,lim,1);
        for(register int i=n;i<lim;++i)g[i]=0;
        NTT(g,lim,0);
        y>>=1;
    }
    NTT(F,lim,1);
    for(register int i=0;i<n;++i)g[i]=F[i],F[i]=0;
    for(register int i=n;i<lim;++i)g[i]=F[i]=0;
}
int fac[maxn]={1},inv[maxn],f[maxn];
inline int calc(int n,int m){
    memset(f,0,sizeof f);
    for(register int i=0;i<m;++i)f[i]=inv[i];
    Pow(f,n-1,n);
    return 1ll*fac[n-2]*f[n-2]%mod;
}
int main(){
    int n=read(),m=read(),t=max(n,m);
    for(register int i=1;i<=t;++i)fac[i]=1ll*fac[i-1]*i%mod;
    inv[t]=quickpow(fac[t]);
    for(register int i=t-1;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    printf("%d\n",qm(calc(n,m)+mod-calc(n,m-1)));
}