[BZOJ]1005: [HNOI2008]明明的煩惱

01-29

lydsy.com-(非許可權)1005: [HNOI2008]明明的煩惱

paste.ubuntu-ARZhus code

在很久很久以前，某金外生在luogu的金外團隊上放了一道題目，問CnH(2n+2)類烷烴有幾種同分異構體。後來思考了一下，並沒有想出來怎麼做。知道做到了這一題目，發現上述問題的本質就是和這道題目一樣——規定一些點的度數，問有幾種不同形態的無根樹。

一開始並不知道如何做，枚舉樹的重心？很顯然我不會做啊所以果斷搜題解。結果發現了一個東西：prufer數列。放下結論：prufer數列的排列和有根樹的形態一一對應。

prufer數列的構造和重構

構造：一棵定點數為V的無根樹，取度為1的編號最小的點，將其連接的點記錄入prufer數列，並將這個點刪去。直到這棵樹還剩兩個點。

重構：取出當前prufer數列中的第一個數，與編號最小的不在prufer數列中頂點連線，並刪去prufer數列中的第一個點。

很顯然，重構和構造互為逆操作，並且對於任意一個數列，都可以轉化成一棵無根樹。並且可以發現一個神奇的性質：在prufer數列中出現次數等於這個節點的度減去1.那麼我們可以把這一道題目轉化成求序列個數來做了。

求解數列

首先考慮沒有-1，即度有限制的情況下。設總共有 $n$ 個頂點，其中有 $k$ 個頂點有限制，那麼 $tot=sum_{i=1}^{k} d_i-1$ ，那對這 $tot$ 個中，排列數是 $C_{tot}^{d_i-1}cdot C_{tot-(d_i-1)}^{d_2-1}cdots C_{d_k-1}{d_k-1}$ 種。然後對於 $tot$ 在所有數中的排列，仍然再乘上 $C_{n-2}^{tot}$ 。對於沒有限制的點，直接有 $(n-k)^{n-2-tot}$ 種。那麼最終答案就是這些東西乘起來。