prufer 序列，簡單來說就是 \(n\) 個節點的樹雙射一個長度 \(n-2\) 值域 \([1,n]\) 的序列。

構造過程就是每次刪一個編號最小葉子，記錄其父節點。

本圖來自baoziwu2,侵刪

顯然堆 \(n\log n\) 可做，也可以掃一遍所有標號，對于已經刪除的父節點，判斷其度數和標號是否該選，分討可做 \(O(n)\)

然后有定理：

\(k\) 個點完全圖有 \(k^{k-2}\) 棵生成樹。

\(n\) 個點的圖有 \(k\) 個聯通塊，第 \(i\) 個聯通塊點數為 \(s_i\) ，添加 \(k-1\) 條邊使其聯通，有 \(n^{k-2}\times \prod\limits_{i=1}^ks_i\) 種方案。

證明可以考慮縮點后為生成樹，考慮每個聯通塊內的點個數，可以得到。

例題 P6596 How Many of Them

updata：找到板子了 CF156D

圖——from STA_Morlin 為什么不讓折疊捏？？？