叶子不区分的建树顺序 — 题解¶
出题人给出容斥与第二类斯特林数的方向。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\) 个标签的满射数：
容斥的理由是：选择 \(j\) 个标签禁止出现后，还剩 \((t-j)^L\) 个序列。对缺失标签事件交替加减，恰好保留没有缺失标签的序列。
每棵树的 \(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<n\) 可能成立。合法大规模情况下，时间 \(O(n+(n-m)\log n)\) ，空间 \(O(n)\) .小规模独立验证使用第二类斯特林数递推 \(S(L,t)=tS(L-1,t)+S(L-1,t-1)\) 与真实树/边序枚举；这类二次动态规划不作为全范围推荐程序。
去掉叶子名字，但保留边序¶
对固定非叶子标签集合，有 \(m!\) 种重命名叶子的方法。对 \(n\ge3\) ，每个叶子的邻居一定是非叶子。假如一个重命名使整条加边序列保持不变，那么每片叶子的唯一边必须保持在同一个添加时刻；其非叶邻居又不能改名，因此这片叶子只能映到自身。
所以只有恒等重命名能固定一条记录。每个等价类恰有 \(m!\) 条带标号记录，答案为
不同非叶子标签集合始终分别计数，所以不能删掉 \(\binom nm\) .也不能把树视为所有顶点均无标号。
\(n=2,m=2\) 时，交换两个叶子保持唯一的无向边不变，上述自由作用证明不成立；这个情况必须直接输出一。\(n=0,1\) 也直接处理。除去这些边界，轨道大小证明与标号记录公式共同保证答案正确，复杂度不变。见 std.cpp。