按顺序连成树：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

正确性¶

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

实现、复杂度与来源¶

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

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