树型DP

• 状态表示：$f[i][j]$表示，当前深度≤$i$，节点数为$j$的树的方案数

• 状态划分：若当前需要插入两个节点，这两个节点可以插入的位置数取决于当前这棵树的形态数，那么当前这棵树的形态则取决于左右子树的形态数，即：左子树的形态数*右子树的形态数。因此$f[i][j]$可以根据当前这棵树的左子树大小划分为$j-1$个状态。

• 状态转移方程：$f[i][j] = \sum_{k=1}^{j-1}{f[i - 1][k] * f[i - 1][j - k - 1]}$ (计算右子树还得减掉根节点)

#include <iostream>

using namespace std;

const int N = 1010 , mod = 9901;

int n , m;
int f[N][N];//f[i][j]表示，当前深度≤i，节点数为j的树的方案数

int main()
{
    cin >> n >> m;

    for(int i = 1 ; i <= m ; i++)//因为深度是≤i，因此f[i][1]都包含f[1][1]这种情况
        f[i][1] = 1;

    for(int i = 1 ; i <= m ; i++)
        for(int j = 1 ; j <= n ; j += 2)//因为加的节点数是0或2，因此递增2
            for(int k = 1 ; k < j ; k += 2)
                f[i][j] = (f[i][j] + f[i - 1][k] * f[i - 1][j - k - 1]) % mod;

    cout << (f[m][n] - f[m - 1][n] + mod) % mod << endl;
}