# 按顺序连成树：Prüfer 序列与边排列

## 先确定最终结构

当 $n\ge2$ 时，任意两点之间恰有一条简单路径，等价于最终图是树。每棵树有 $n-1$ 条边，这些边可以按任意顺序加入，产生 $(n-1)!$ 个不同序列。任意前缀也是森林，不会使后续加入变得非法。

## 用 Prüfer 序列计数树

对一棵带标号树，重复删除当前编号最小的叶子，并记录它的邻居，直到只剩两个顶点。得到长度为 $n-2$ 的序列，每个位置可取任意顶点编号。

反过来，给定这样的序列，令每个顶点的度数等于一加上它在序列中的出现次数。每读一个编号 $v$ ，选出当前度数为一的最小顶点 $u$ ，连边 $(u,v)$ 并删除 $u$ ，将 $v$ 的度数减一。最后连接剩余两个顶点。每一步至少存在一个度数为一且不在未读序列中的顶点，过程确定；删除叶子的编码与此解码互为逆操作。

所以带标号树与长度 $n-2$ 的 Prüfer 序列一一对应，树的数量为 $n^{n-2}$ .最终答案是

$$n^{n-2}(n-1)!\pmod{998244353}\qquad(n\ge2).$$

$n=0$ 或 $n=1$ 时只有空操作序列，答案是一；$n=2$ 也为一。无需使用负指数公式。

![Two orders of the same tree](assets/orders.svg)

## 正确性

每个合法加边序列唯一确定一棵带标号树和该树边的一个排列。反之，任意树与任意边排列都产生合法序列。Prüfer 双射给出树数，排列给出每棵树的顺序数，故二者相乘恰好不重不漏地统计所有答案。

## 实现、复杂度与来源

逐项相乘计算阶乘，二进制快速幂计算 $n^{n-2}$ ，每次乘积及时取模。两个剩余的乘积小于 $998244353^2<2^{63}$ ，使用标准 64 位整数即可。时间 $O(n+\log(n+1))$ ，额外空间 $O(1)$ ；只保留阶乘的当前乘积。

出题人解法采用 Cayley 公式与边排列；Prüfer 双射是该经典公式的证明。GPT-6 补全双语证明、空图边界解释和常数空间实现。[std.cpp](std.cpp) 为首选。矩阵树定理对本题会增加计算和实现成本，未形成相同范围下的独立优势，故不另列程序。小规模枚举边集并用并查集验证树，再枚举排列数量；大规模用独立乘积树核对。性能见[测量记录](../../../docs/benchmark-R24.json)。