CodeForces Contest #110 D

題目: http://codeforces.com/contest/156/problem/D

不難看出是數 spanning trees 的數目
處理本身已有的 edge, 先把 G 看成是一個個的 component, 入面是怎樣連接並不重要
得到一個 |C| 個 component 的 complete graph, 但是每個 component 都是有 weight 的

使用 Prüfer's sequence 的變種可以解決
把每棵 spanning tree map 成一條 |V|^(|C|-2) 的 sequence
(不是 1 : 1 mapping)

Spanning Tree → Sequence:
先把每個 component label 1, 2, .., |C|
每次選取 label 最小的 leaf, 寫下它連接的 vertex label, 然後 remove leaf component
直至剩下 2 個 component

過程中有些 information 是 lost 了的
remove leaf component 時, 並沒有記錄 edge 在 leaf component 是連接哪個 vertex
以及最後剩下兩個 component 相連的 edge 的連接方法

所以每條 sequence 其實對應著 Π|c_i| 棵 spanning tree

Sequence → Spanning Tree:
雖然每條 sequence 並不對應唯一的 spanning tree, 但是使用原本的方法也必定可以還原出一棵 "不確定的" spanning tree
所謂的不確定就是上面所說的 Π|c_i|

所以答案是 |V|^(|C|-2) * Π|c_i|