以下 \(d_i\) 表示 \(i\) 的度数。
Prufer 序列完成了一个有标号无根树与序列的双射。长度为 \(n-2\) 的值域 \([1,n]\) 的序列一一对应一棵 \(n\) 个点的有标号无根树。
构建序列的方式就是每次找编号最小的叶节点，然后把它连接的点加入序列，然后删掉这个叶节点。
原因是什么我也不会证，貌似也不需要会证（？）
有几个结论，在与数树相关的题目时会比较有用。
-
\(n\) 个点的有标号无根树有 \(n^{n-2}\) 棵，有标号有根树有 \(n^{n-1}\) 棵。
-
Prufer 序列中 \(u\) 出现的次数为 \(d_u-1\)。
-
构建 Prufer 序列最后没删掉的点其中有一个为 \(n\)。