给出标号为 1 1 到 N N 的点，以及某些点最终的度数，允许在任意两点间连线，可产生多少棵度数满足要求的树？

题解

首先要知道一个叫「prufer序列」的东西。

首先，从有标号无根树生成「prufer序列」的方法我就不瞎逼逼了。 其次，一个「prufer序列」唯一对应一棵有标号无根树。 再次，一棵 n n 个节点的有标号无根树的「prufer序列」的长度为 n−2 n - 2 ，树中度为 d d 的点在「prufer序列」中的出现次数是 d−1 d - 1 。

设一共有 k k 个被限制度的点，di d_i 为第 i i 个节点的度，s=∑di≠−1di s = \sum\limits_{d_i \neq -1} d_i ，表示被限制度的点在序列中出现了 s s 次。

考虑这些点的位置：

C(n−2,s)s!∏di≠−1(di−1)! C(n - 2, s)\frac { s! } {\prod\limits_{d_i \neq -1} (d_i - 1)!}

对于序列中剩下的 n−2−s n - 2 - s 个点，就可以随便放了，所以整体上就是

s!C(n−2,s)(n−k)n−2−s∏di≠−1(di−1)! \frac {s!C(n - 2, s)(n - k) ^ {n - 2 - s}} {\prod\limits_{d_i \neq -1}(d_i - 1)!}

上式化简得:

(n−2)!(n−k)n−2−s(n−2−s)!∏di≠−1(di−1)! \frac {(n - 2)!(n - k) ^ {n - 2 - s}} {(n - 2 - s)!\prod\limits_{d_i \neq -1} (d_i - 1)!}

代码不想贴了。。我羞耻的没有写高精度。。