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了

送出記錄