A. 圣诞树
和度数相关的数树题可以考虑 prufer 序列。
prufer 序列的性质是，一个数在其中出现次数加一是其度数。
如果称一个点上孔的数量为 \(a_i\)，称一种情况中 i 点的度数是 \(d_i\)，那么我们的答案就是：
\[\displaystyle\sum_{\sum {d_i - 1 = n - 2}} \binom{n - 2}{d_1 - 1} \binom{n - 2 - (d_1 - 1)}{d_2 - 1} ..... \binom{b_n - 1}{b_n - 1} \prod_{i = 1}^n a_i^{\underline{d_i}}
\]
可以发现，前面的组合数相乘的部分就是：
\[(n - 2)!\sum_{\sum {d_i - 1 = n - 2}} \prod\frac{1}{(d_i - 1)!}
\]
考虑把后面两项合并：
\[(n - 2)!\sum_{\sum {d_i - 1 = n - 2}} \prod\frac{a_i!}{(d_i - 1)!(a_i - d_i)!}
\]
后面的东西很像组合数：
\[(n - 2)!\sum_{\sum {d_i - 1 = n - 2}} \prod a_i\frac{(a_i - 1)!}{(d_i - 1)!(a_i - d_i)!}\\
\Leftrightarrow (n - 2)!\prod a_i \sum_{\sum {d_i - 1 = n - 2}} \prod \binom{a_i - 1}{d_i - 1}
\]
考虑组合意义，后面的东西就是：
\[(n - 2)!\prod a_i \sum_{\sum {d_i - 1 = n - 2}} \binom{\sum( a_i - 1)}{\sum (d_i - 1)}\\
\Leftrightarrow
(n - 2)!\prod a_i \binom{\sum( a_i - 1)}{n - 2}
\]
直接计算即可。
B. 序列
我们从值域的角度去想，如果我当前将所有大于 i 的数已经加进去了，现在我们要将所有的 i 插入这个序列中。
考虑如果现在我有 j 个连续段，那么如果我插入一个 i 不使段数增加，那么必须插在段尾，否则 i 会使段数增加。
我可以枚举不使段数增加的 i 有 x 个，剩下 \(a_i - x\) 个要插进原本连续段的两个数中间去，使连续段增加 \(a_i - x\) 个。
因为可以有两个 i 插入一个缝中，所以我们考虑插板法。
一共 \(a_i - x\) 个数，\(\sum_{t = i}^n a_t - j + x\) 个板。
则方程为
f[i][j + a[i] - x] += f[i][j] * C(j, x) * C(sum[i + 1] - j + x, sum[i + 1] + a[i] - j)