我是SB TAT

我发现我根本不会树的计数

其实我只会有度数限制，并且度数限制比较小的做法

对于没有度数限制的树的计数直接看论文吧

反正我是看不懂TAT

【写在前面】：
    之前看了%%%Nanoape的blog后一直想搞懂的东西
    然后上百度搜了一发教程，发现了一个用&$^^&^$%^微分^$%^$%积分^$^解决的办法(-_-|||)
    然后就弃疗了
    昨天在跟dwj讨论了一发，然后膜了膜大神们的代码，大概搞懂了
【参考】：

《无根树的计数统计》 By 赵爽

【问题简述】：
    树的计数分为两种：
    1.有根数计数
    2.无根树计数
    但是两者的解法大致相同
    本文就分这两类问题进行讨论
【有根数计数】：
    题目大意：给出n K，求出n个节点的有根树且每个点度数不超过K (n<=1000 K<=10)
    我们考虑动态规划
    f[i][j][k]表示i个点最大的子树大小为j子树个数为k的方案数
    g[i]表示i个点构成的根节点度数<K的有根树个数
    f[i][j][k]=f[i-j*t][j-1][k-t]*C(g[j]+t-1,t)
    g[i]=sigma(f[i][j][k]) (k<K)
【无根树计数】：
    看了上面论文的图片，你就应该明白无根树和有根数的区别了吧
    因此我们先考虑单个重心的情况，也就是说根节点的子树大小不超过(n-1)/2
    然后同样dp一发就可以了
    F[i][j][k]表示i个点最大的子树大小为j子树个数为k的方案数
    F[i]表示i个点构成的根节点度数<=K的有根树个数
    F[i][j][k]=F[i-j*t][j-1][k-t]*C(g[j]+t-1,t)
    G[i]=sigma(F[i][j][k]) (k<=K)

    然后考虑双重心的情况
    考虑这样的情况只可能n为偶数
    此时变成了一颗有两颗大小为n/2的子树构成的树
    那么方案数就加上g[n/2)*(g[n/2]+1)/2即可
【总结】：
    由此看出，在这样的问题中复杂度为O(N^2*K^2)
    在N,K不大时可以胜任
    大概就是这样喽

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1005;
const int M=15;
const long long maxmod=998244353;
int n,m,S,ans,f[N][N][M],g[N],F[N][N][M],G[N];
long long fac[M],inv[M];
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
inline long long calc(long long x,long long y)
{
    long long nowans=1;
    for (;y;y/=2,x=x*x%maxmod) if (y&1) nowans=nowans*x%maxmod;
    return nowans;
}
void init()
{
    n=getint(); m=getint(); S=(n-1)/2; fac[0]=1; inv[0]=1;
    for (int i=1; i<=m; i++) fac[i]=fac[i-1]*i%maxmod;
    for (int i=1; i<=m; i++) inv[i]=inv[i-1]*calc(i,maxmod-2)%maxmod;
}
inline void add(int &a,long long b)
{
    b%=maxmod;
    a=a+b; if (a>=maxmod) a-=maxmod;
}
inline long long C(int n,int m)
{
    long long nowans=inv[m];
    for (int i=1; i<=m; i++)
    {
        nowans=nowans*n%maxmod;
        n--; if (n<0) n+=maxmod;
    }
    return nowans;
}
namespace NoRootDP
{
    void solve()
    {
        f[1][0][0]=1; g[1]=1;
        for (int j=1; j<=n; j++) add(f[1][j][0],f[1][j-1][0]);
        for (int i=2; i<=n; i++)
        {
            for (int j=1; j<=i-1; j++)
                for (int k=1; k<=m; k++)
                    for (int t=1; t<=k; t++)
                    {
                        if (j*t>i-1) break;
                        add(f[i][j][k],(long long)f[i-j*t][j-1][k-t]*C(g[j]+t-1,t)%maxmod);
                    }
            for (int k=1; k<=m; k++) for (int j=1; j<=n; j++) add(f[i][j][k],f[i][j-1][k]);
            for (int k=1; k<=m-1; k++) add(g[i],f[i][i-1][k]);
        }
    }
}
namespace HaveRootDP
{
    void solve()
    {
        F[1][0][0]=1; G[1]=1;
        for (int j=1; j<=n; j++) add(F[1][j][0],F[1][j-1][0]);
        for (int i=2; i<=n; i++)
        {
            for (int j=1; j<=min(S,i-1); j++)
                for (int k=1; k<=m; k++)
                    for (int t=1; t<=k; t++)
                    {
                        if (j*t>i-1) break;
                        add(F[i][j][k],(long long)F[i-j*t][j-1][k-t]*C(g[j]+t-1,t));
                    }
            for (int k=1; k<=m; k++) for (int j=1; j<=n; j++) add(F[i][j][k],F[i][j-1][k]);
            for (int k=1; k<=m; k++) add(G[i],F[i][i-1][k]);
        }
    }
}
void solve()
{
    ans=G[n]; if (n%2==1) {printf("%d\n",ans); return;}
    add(ans,(long long)g[n/2]*(g[n/2]+1)%maxmod*inv[2]%maxmod);
    printf("%d\n",ans);
}
int main()
{
    init();
    NoRootDP::solve();
    HaveRootDP::solve();
    solve();
    return 0;
}