Prufer 序列构造了一个 $n \geq 2$ 个结点的无根树，与一个长度为 $n - 2$、值域在 $[1, n]$ 的序列之间的双射。
每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。重复 $n - 2$ 次后就只剩下两个结点，算法结束。
显然剩下结点中一定有 $n$。
根据 Prufer 序列的性质，我们可以得到原树上每个点的度数。然后你也可以得到度数最小的叶结点编号，而这个结点一定与 Prufer 序列的第一个数连接。然后我们同时删掉这两个结点的度数。
讲到这里也许你已经知道该怎么做了。每次我们选择一个度数为 $1$ 的最小的结点编号，与当前枚举到的 Prufer 序列的点连接，然后同时减掉两个点的度。到最后我们剩下两个度数为 $1$ 的点，其中一个是结点 $n$。
我们知道 Prufer 序列可以得到 Cayley 公式，即带标号无根树的个数是 $n^{n-2}$ 的，因为对应的 Prufer 序列就有这么多种。同时由于 Prufer 序列还体现了树中度数的关系，因此也可以用来做一些度数有限制的生成树计数。例如，设已知节点的度数组 $d_1, d_2, \ldots, d_n$，则其无根树的数量为
$$ \dfrac {(n-2)!}{\prod_{i=1}^n (d_i - 1)!} $$
证明只要考虑“度为 $d$ 的节点会出现 $d-1$ 次”这个性质即可。另一个带度数限制的例子可以参考 Valuable Forests 这道题的树形 DP 解法。