草稿纸（这是真的）
DE_aemmprty
·
·
个人记录
ZR3422
:::info[问题 1]{open}
给定两个排列 a 和 b，其中 a 大小为 n，b 大小为 m。
现在你需要对长度为 n + m 的排列 c 计数，要满足：
:::success[Sol 1]
答案是 \binom{n + m}{n}。易证。
:::
:::info[问题 2]{open}
给定两棵树 a 和 b，其中 a 大小为 n，b 大小为 m。
现在你需要对大小为 n + m + 1 的树 c 计数，要满足：
:::success[Sol 2]
答案是 \binom{n + m}{n}。其实和上一个一样。
:::
:::info[问题 3]{open}
回到原题。
设 f_{u, x} 表示以 1 为根，大小为 u，深度为 x 的树。
转移是每次给这棵树加入一颗新的子树，假设新的子树大小为 p，深度为 q，则有转移：
f_{u, x}f_{p, q}\binom{u + p - 1}{p} \to f_{u + p, \max\{x, q\}}
上面的转移有问题，问题在哪。
:::
:::error[Sol 3]
假设有两种子树，A, B，我们加入子树的顺序可能是 AB，也可能是 BA，会导致算重复。
:::
:::info[问题 4]{open}
如何去重。
:::
:::success[Sol 4]
加条件。假设加入的子树是从 p_1 到 p_k 按顺序加入的，那么我们令这些子树的最大编号是递增的。
就是每次加入新的子树，我们强制令这个子树的最大编号是整棵树的最大编号。
新的转移式就是新家的子树少了一个点（最大编号那个点被固定了），因此是：
:::
:::info[问题 5]{open}
复杂度过大，考虑优化。
:::
:::success[Sol 5]
我们枚举 $u, p, t = \max\{x, q\}$，那么就有：
$f_{u + p, t} = (\sum_{x = 0}^{t}f_{u, x}f_{p, t} + \sum_{q = 0}^{t - 1}f_{u, t}f_{p, q})\binom{u + p - 2}{p - 1}
使用前缀和优化即可。
:::
:::info[BONUS]{open}
其实上面的常数有点大（我过不了），因此有一种更牛的 DP。
我们将深度为 x 的树的个数转化为深度 \leq x 的树的个数。
设 f_{u, x} 表示大小为 u，根节点编号为 1，深度 \leq x 的树的个数。
这样的好处是拼上一个子树可以直接使用 f_{p, x - 1}，不用前缀和优化。还算简单，自己研究。
:::