Prufer序列的转化方法见这篇博客（这篇文章里这道模板题的高精处理方法也看看）
这里主要是对这篇博客的一些说明。
首先：为什么Prufer序列与无根树一一对应？
我们要先知道两个引理：出现在Prufer序列中的点一定是原无根树的非叶子节点，没有出现在Prufer序列中的一定是原无根树的叶子节点
第一个引理比较简单，因为他根本没有儿子节点让他被添加到Prufer序列中
第二个引理，我们用反证。设某个原无根树的非叶子节点没有被添加到Prufer序列中。
如果这个节点已经被删除了（不是最后剩下的那两个节点中的其中一个），那么在这个节点被删除的时候，它一定只剩了一条边。由于它原来不是叶子节点，所以他最开始的边是多于一条边的，那么这些边任何一个被删除的时候都会把这个点添加到Prufer序列中，矛盾
如果这个节点是最后剩下的两个中的其中一个，那么这个点最后只剩下了一条边，同理，他在删除任何一条边的时候都会被添加到Prufer序列中，矛盾
综上，两个引理得证
那么我们在还原的时候，就可以按照这篇博客里面说的去还原了，肯定就是对的了
注意在还原的过程中，由于每个点只会被删除一次，所以如果某个点在经过这次还原后已经不再Prufer序列里面了，一定要在非Prufer序列集合里面增加这个点。因为对此时剩下的图来说，这个点已经是叶子节点了
那么我随便写一个Prufer序列一定都是合法的吗？
答案是肯定的。因为Prufer序列的长度是n-2，假设我们已经还原了k个节点，那么按照博客里面的方法，至多还有n-k个节点没有被选择，然而此时Prufer序列里面只有n-2-k个节点，即没有被选择的节点至少还有两个可以选择，所以在任意时刻都不会找不到供选择的节点
标签：删除,还原,序列,引理,Prufer,节点 From： https://www.cnblogs.com/dingxingdi/p/17738964.html