最近做到一些題，用到了Prufer序列，挺有用的，在這里學(xué)習(xí)一下。

描述

Prufer數(shù)列是無根樹的一種數(shù)列，通過一個(gè)Prufer序列可以唯一表示一棵頂點(diǎn)帶標(biāo)號(hào)的無根樹，點(diǎn)數(shù)為n的樹轉(zhuǎn)化來的Prufer數(shù)列長(zhǎng)度為n-2，它有很多的性質(zhì)

求法

一種生成Prufer序列的方法是迭代刪點(diǎn)，直到原圖僅剩兩個(gè)點(diǎn)。對(duì)于一棵頂點(diǎn)已經(jīng)經(jīng)過編號(hào)的樹T，頂點(diǎn)的編號(hào)為{1,2,…,n}，在第i步時(shí)，移去所有葉子節(jié)點(diǎn)（度為1的頂點(diǎn)）中標(biāo)號(hào)最小的頂點(diǎn)和相連的邊，并把與它相鄰的點(diǎn)的編號(hào)加入Prufer序列中，重復(fù)以上步驟直到原圖僅剩2個(gè)頂點(diǎn)
可以發(fā)現(xiàn)，對(duì)于一棵帶標(biāo)號(hào)的無根樹的Prufer序列是唯一的

轉(zhuǎn)回

現(xiàn)在有一個(gè)prufer序列，如何推回原本的無根樹呢？
考慮對(duì)于初始的點(diǎn)集1~n，根據(jù)生成的方式可以得知，第一個(gè)刪掉的點(diǎn)在之后一定不會(huì)出現(xiàn)，而未出現(xiàn)的點(diǎn)都是一開始度數(shù)為1的，所以說，第一個(gè)被刪除的點(diǎn)的編號(hào)是所有開始未出現(xiàn)的點(diǎn)中編號(hào)最小的，刪除一個(gè)點(diǎn)后就可以轉(zhuǎn)化為子問題了，直到昨晚n-2次，此時(shí)對(duì)未被刪除的剩下兩個(gè)點(diǎn)連上一條邊，就把原樹構(gòu)造出來了
容易發(fā)現(xiàn)，一個(gè)Prufer序列對(duì)應(yīng)著唯一的一個(gè)帶標(biāo)號(hào)的無根樹

作用

比如，現(xiàn)在有一棵$n$個(gè)節(jié)點(diǎn)的樹，給定每個(gè)節(jié)點(diǎn)的度數(shù)，求樹可能形態(tài)數(shù)，答案為：$$\frac{(n?2)!}{{\prod }_{i=1}^n(d_i?1)!}$$
然后如果有些節(jié)點(diǎn)如果不確定度數(shù)也可以做
例題：[HNOI2008][bzoj1005]明明的煩惱（咕咕咕咕咕）

---

待upd

---

總結(jié)

以上是生活随笔為你收集整理的Prufer序列相关的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。