Prufer 序列

定義與建立

Prufer 序列可以將一個(gè)帶標(biāo)號(hào) \(n\) 個(gè)結(jié)點(diǎn)的樹用 \([1,n]\) 中的 \(n-2\) 個(gè)整數(shù)表示。一個(gè)無向帶標(biāo)號(hào)生成樹與數(shù)列之間的雙射。

對(duì)于一棵樹，每次我們選擇它編號(hào)最小的葉子結(jié)點(diǎn)，刪除它并記錄下與它相連的節(jié)點(diǎn)的編號(hào)，那么最終記錄下的 \(n-2\) 個(gè)數(shù)就組成了這棵樹的 Prufer 序列。

顯然用這個(gè)東西維護(hù)樹的結(jié)構(gòu)感覺非常不好，這個(gè)東西主要用來數(shù)數(shù)用的。

對(duì)樹建立 Prufer 序列

按照定義直接建立，那么每次從堆中取出最小的數(shù)，刪去它并記錄。

這樣可以得到一個(gè) \(\mathcal{O(n\log n)}\) 的做法，但是顯然這不夠優(yōu)美，我們需要一個(gè) \(\mathcal{O(n)}\) 的解法。

我們發(fā)現(xiàn)剩余的葉子結(jié)點(diǎn)數(shù)量是遞減的，每次刪除要么少一個(gè)，要么少一個(gè)又多一個(gè)。

從小到大枚舉編號(hào) \(p\)，如果是葉子結(jié)點(diǎn)，將和它們相鄰的點(diǎn)放入 Prufer 序列中?？紤]這個(gè)葉子結(jié)點(diǎn)帶來的新葉子結(jié)點(diǎn)：

• 如果和它相鄰的點(diǎn)編號(hào) \(p'>p\) 或者 \(p'\) 沒有變成葉子結(jié)點(diǎn)，那么不用管，它會(huì)在之后被枚舉到。
• 但是如果 \(p'<p\)，它在時(shí)候不會(huì)被枚舉到了。但是發(fā)現(xiàn)刪除之前當(dāng)前最小的葉子結(jié)點(diǎn)是 \(p\)，所以刪后 \(p'\) 必然是最小的葉子，所以可以直接繼續(xù)刪除 \(p'\)。

for(int i=1,x;i<n;i++) x=rd(),add(i,x),add(x,i),ind[i]++,ind[x]++; // [1,n-1] 的父親序列 for(int i=1;i<=n;i++) if(ind[i]==1) exist[i]=true; for(int i=1,p;i<=n;i++) {if(!exist[i]) continue;p=i;while(p<=i){used[p]=true;for(int j=hea[p];j;j=nex[j])if(!used[ver[j]]) { p=ver[j]; break; }if(ind[p]==1) break;ind[p]--,pru[++cnt]=p;if(ind[p]==1) exist[p]=true;if(ind[p]!=1 || p>i) break;}if(ind[p]==1) exist[p]=true; } assert(cnt==n-2); for(int i=1;i<=cnt;i++) ret^=1ll*i*pru[i]; printf("%lld\n",ret);

用 Prufer 還原無根樹

發(fā)現(xiàn) Prufer 序列中的每個(gè)數(shù)的出現(xiàn)次數(shù)就是原樹中每個(gè)點(diǎn)的度數(shù) \(-1\)，可以每次連一個(gè)葉子結(jié)點(diǎn)重構(gòu)。

方法類似，一個(gè)暴力的做法是每次選出最小的當(dāng)前的葉子結(jié)點(diǎn)，將它與 Prufer 序列最前面的元素相連，這樣復(fù)雜度是 \(\mathcal{O(n\log n)}\) 的。

發(fā)現(xiàn)葉子結(jié)點(diǎn)編號(hào)遞增，設(shè)刪去的葉子結(jié)點(diǎn)為 \(p\)，和它相鄰的是 \(p'\)。當(dāng)加完 \(p\) 后 \(p'\) 的度數(shù)變?yōu)?\(1\) 并且 \(p'<p\)，那么它下一次一定被選擇，直接繼續(xù)連邊即可。

for(int i=1;i<=n-2;i++) pru[i]=rd(),ind[pru[i]]++; for(int i=1;i<=n;i++) if(!ind[i]) exist[i]=true; int pos=1; for(int i=1,p;i<=n;i++) {if(!exist[i]) continue;p=i;while(p<=i){if(pos==n-1) { fa[p]=n; break; }fa[p]=pru[pos],p=pru[pos],ind[p]--,pos++;if(pos>=n) break;if(ind[p] || p>i) break;}if(!ind[p]) exist[p]=true; } for(int i=1;i<n;i++) ret^=1ll*i*fa[i]; printf("%lld\n",ret);

主要性質(zhì)

• Prufer 序列與無根樹一一對(duì)應(yīng)(好像比較顯然)

• 度數(shù)為 \(d_i\) 的點(diǎn)在 Prufer 序列中出現(xiàn) \(d_i-1\) 次(上面還用到了這個(gè)結(jié)論)

• 【根據(jù)度數(shù)求方案】對(duì)于給定每個(gè)點(diǎn)度數(shù)為 \(d_i\) 的無根樹，方案數(shù)為：

  \[\dfrac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!} \]

  證明：Prufer 序列長度為 \(n-2\)，每個(gè)數(shù)出現(xiàn)次數(shù)為 \(d_i-1\)，根據(jù)組合意義直接計(jì)算全排列即可。

• 【根據(jù)連通塊數(shù)量與大小求方案】一個(gè) \(n\) 個(gè)點(diǎn) \(m\) 條邊的帶標(biāo)號(hào)無向圖有 \(k\) 個(gè)連通塊，每個(gè)連通塊大小為 \(s_i\)，需要增加 \(k-1\) 條邊使得整個(gè)圖聯(lián)通，方案數(shù)為：(但是當(dāng) \(k=1\) 時(shí)需要特判)

  \[n^{k-2}\cdot\prod_{i=1}^{k}s_i \]

  證明見 OI-wiki

總結(jié)

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

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