Prufer 序列构造了一个 $n \geq 2$ 个结点的无根树，与一个长度为 $n - 2$、值域在 $[1, n]$ 的序列之间的双射。

每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。重复 $n - 2$ 次后就只剩下两个结点，算法结束。

显然剩下结点中一定有 $n$。

根据 Prufer 序列的性质，我们可以得到原树上每个点的度数。然后你也可以得到度数最小的叶结点编号，而这个结点一定与 Prufer 序列的第一个数连接。然后我们同时删掉这两个结点的度数。

讲到这里也许你已经知道该怎么做了。每次我们选择一个度数为 $1$ 的最小的结点编号，与当前枚举到的 Prufer 序列的点连接，然后同时减掉两个点的度。到最后我们剩下两个度数为 $1$ 的点，其中一个是结点 $n$。

1. 在构造完 Prufer 序列后原树中会剩下两个结点，其中一个一定是编号最大的点；
2. 每个结点在序列中出现的次数是其度数减 $1$，没有出现的就是叶结点。

我们知道 Prufer 序列可以得到 Cayley 公式，即带标号无根树的个数是 $n^{n-2}$ 的，因为对应的 Prufer 序列就有这么多种。同时由于 Prufer 序列还体现了树中度数的关系，因此也可以用来做一些度数有限制的生成树计数。

带度数限制的例子可以参考 Valuable Forests 这道题的树形 DP 解法。

• Prufer 序列 - OI Wiki