# 指定叶子数的建树顺序 — 题解 出题人给出容斥与第二类斯特林数的方向。Codex（GPT-6）完成正确的满射计数、边界处理、证明、实现和验证。 ## Prüfer 序列中的叶子 对 $n\ge3$ 的标号树，反复删除最小标号的叶子并记录它的邻居，得到长度 $n-2$ 的 Prüfer 序列。反过来，每次选择尚未出现在剩余序列中的最小标签作为叶子，就能唯一还原树。因此所有长度 $n-2$ 的标签序列与标号树一一对应；标签 $v$ 的出现次数等于 $\deg(v)-1$ . 恰有 $m$ 片叶子，等价于序列恰好使用 $t=n-m$ 种标签，且每种至少出现一次。先选叶子集合，有 $\binom nm$ 种。剩下的问题是长 $L=n-2$ 的序列到指定 $t$ 个标签的满射数： $$U(L,t)=\sum_{j=0}^{t}(-1)^j\binom tj(t-j)^L.$$ 容斥的理由是：选择 $j$ 个标签禁止出现后，还剩 $(t-j)^L$ 个序列。对缺失标签事件交替加减，恰好保留没有缺失标签的序列。 每棵树的 $n-1$ 条不同边都可以任意排序；任何树边子集都无环，故中途没有额外限制。带标号的加边记录数为 $$B(n,m)=\binom nm U(n-2,n-m)(n-1)!.$$ ## 为什么不能用相邻两项相减 $\binom nm(n-m)^{n-2}$ 统计的是“树与选定的 $m$ 片叶子集合”这一对对象。一棵实际有 $\ell$ 片叶子的树被数了 $\binom\ell m$ 次，不能把它当成“至少有 $m$ 片叶子的树数”。相邻两项相减仍有重数。 例如 $n=4,m=2$ ，错误相减再乘 $3!$ 得到 $120$ ；真正的两叶树是 $4!/2=12$ 条无向路径，各有 $3!=6$ 种边序，总共 $72$ .错误方法还额外计入星形树。这说明需要完整容斥或满射计数。 ## 实现与复杂度 模数 $p=998244353$ 为素数，所有需要的阶乘参数都小于 $p$ .预处理阶乘和逆阶乘，用一次快速幂求最大阶乘的逆元，再倒推，便可常数时间计算组合数。每项幂用二进制快速幂，交替项始终归一化到非负剩余。 $n\le2$ 直接按题面输出一或零。$n\ge3$ 时，只有 $2\le m