Prüfer sequence

结点编号为1,2,3....,n(n >= 2)的一棵树对应的prufer sequence是长度为n - 2的一个序列（序列元素为{1,2,...,n}，于是生产树的总数为n^(n - 2)。

 

prufer sequence的产生方法：

将树的叶子结点逐个剥去，直至剩下两个结点。

剥第k个：取出当前的叶子编号最小的结点，设为y，设它的邻居的结点编号为x，设置ps[k] = x，剥去y。

显然树的形态和prufer sequence是一一对应的。

所以结论成立！