BZOJ 1005: [HNOI2008]明明的煩惱
Description
自從明明學了樹的結構,就對奇怪的樹產生了興趣......給出標號為1到N的點,以及某些點最終的度數,允許在
任意兩點間連線,可產生多少棵度數滿足要求的樹?
Input
第一行為N(0 < N < = 1000),
接下來N行,第i+1行給出第i個節點的度數Di,如果對度數不要求,則輸入-1
Output
一個整數,表示不同的滿足要求的樹的個數,無解輸出0
Sample Input
3
1
-1
-1
Sample Output
2
HINT
兩棵樹分別為1-2-3;1-3-2
Source
Solution
引出知識點prufer編碼（摘抄一段定義）：
[1]樹的prufer編碼的實現
? 不斷 刪除樹中度數為1的最小序號的點，并輸出與其相連的節點的序號 直至樹中只有兩個節點
[2]通過觀察我們可以發現
? 任意一棵n節點的樹都可唯一的用長度為n-2的prufer編碼表示
? 度數為m的節點的序號在prufer編碼中出現的次數為m-1
[1] 怎樣將prufer編碼還原為一棵樹？？
? 從prufer編碼的最前端開始掃描節點，設該節點序號為 u ,尋找不在prufer編碼的最小序號且沒有被標記的節點 v ，連接 u,v,并標記v，將u從prufer編碼中刪除。掃描下一節點。
先考慮沒有-1的情況，已知cnt個點的讀數，把他們放進n-2個格子的個數?
\[ \frac{(n-2)!}{(n-2-cnt)!\prod_{i=1}^n(d_i-1)!} \]
剩下的隨便放入剩下的n-2-cnt個格子種，即：
\[ Ans=\frac{(n-2)!}{(n-2-cnt)!\prod_{i=1}^n(d_i-1)!}(n-cnt)^{n-2-sum} \]
注意：高精度可能超時，要分解質因數最后把因數相乘即可。
代碼就不貼了，太丑了。
)
