prufer序列

【算法简介】

prufer序列就是，将一个带标号有根树和n-2个点值域在[1,n]的一个双射   这不重要

建立方式：

每次选择一个编号最小的点删除，然后找到这棵树的叶节点标号最小的一个，在序列中记录下这个叶节点连接的那个点（父亲），重复n-2次即可

构建一个指针p，初始把它直到最小的叶子节点

然后循环进行一下操作：

1.删除当前p指向的节点

2.如果产生新的节点，设这个节点编号为x，如果x>p，不做其他操作；否则删除x，检查是否出现新的叶子节点，重复步骤2

3.增加指针p直到指向一个未被删除的叶节点

性质：

1.剩下的2个节点中有一个为n

2.每个节点出现的次数是其度数-1

利用prufer序列构建重构树：

仍然有线性的构造方法，与当前枚举到的 Prufer 序列的点连接，然后同时减掉两个点的度。到最后我们剩下两个度数为 的点，其中一个是结点 。就把它们建立连接。

Prufer 序列的方法。在删度数的时侯会产生新的叶结点，于是判断这个叶结点与指针p的大小关系，如果更小就优先考虑它

其实我们更多的会用到prufer序列的度数性质，来进行计数

【例题】P2290 [HNOI2004]树的计数

提交记录

【习题1】P2624 [HNOI2008]明明的烦恼

这是个需要高精的题，那我们就必然用python了

提交记录