题解

思路

标号树与 Prüfer 序列一一对应。含 $n$ 个节点的树对应一个长度为 $n-2$、元素属于 $1$ 到 $n$ 的序列；节点 $i$ 在序列中恰好出现 $d_i-1$ 次。

当 $n>1$ 时，合法树必须满足每个 $d_i\ge1$ 且 $\sum d_i=2(n-1)$。满足条件时，问题等价于计算指定每种数字出现次数的多重集合排列数：

由于不能在模意义下做除法，且答案需要精确输出，满分做法分解分子和分母中每个质数的指数，再将剩余质因子乘回。

做法

• $n\le8$：枚举全部 $n^{n-2}$ 个 Prüfer 序列，统计每个编号的出现次数并与给定度数比较。
• $\max d_i\le2$：合法树只能是一条路径。若 $n>1$ 时恰有两个度数为 $1$ 的端点、其余度数为 $2$，答案为 $(n-2)!$；否则为零。
• 无限制：验证度数条件后，用 Legendre 公式累计每个质数在阶乘中的指数。

特别地，$n=1$ 时只有一棵单节点树，它的度数为 $0$。

证明

Prüfer 编码与带编号无根树之间是双射，且删除叶子生成编码的过程中，节点 $i$ 被记录的次数恰为它被删成叶子前损失的边数，即 $d_i-1$。因此，满足指定度数的树数等于包含 $d_i-1$ 个数字 $i$ 的 Prüfer 序列数。

当所有度数为正且度数和为 $2(n-1)$ 时，所有重复次数非负且总和为 $n-2$，多重集合排列公式给出上述答案；若条件不成立则不存在树。素因子指数法只是对这个整数公式做精确约分，不改变其值。

复杂度

满分算法枚举不超过 $150$ 的质数并计算阶乘指数，时间复杂度为 $O(n\pi(n))$，空间复杂度为 $O(\pi(n))$。