最小度限制生成樹

http://codeforces.com/gym/100227/submission/4751186
http://www.csie.ntnu.edu.tw/~u91029/SpanningTree.html

約定結點 1 為度限制的結點。。度限制為至多 K。

先不考慮這個結點,求生成森林。(Kruskal 的話還是一趟。)。之後從 1 開始向每個森林連邊(dfs1)
。則第一階段結束後 1 。我們得到了一個度限制為 K0 的最小生成樹。。(初始生成森林的連通塊個數)
要想進一步得到度限制為 K 的最小生成樹,還需要進行 K - K0 次 「差額最小添刪操作" ...

... 其實就是貪心替換、、。。設 w1[u] 為 u 結點連到根結點的邊的權值(可能輸入的時候有重邊。。保留最小的。)
。 從根結點 dfs2 下去。。得到每個結點到根結點路徑刪最大的邊的權值和編號。mx[u], si[u]。
。。則選擇 u 結點進行替換的話。。產生的收益就是 mx[u] - w1[u] 。。。枚舉每個結點。。找出收益最大的。
。。迭代 K - K0 次即可。。(若某輪收益已經為 0。。則可直接 break 掉。。)

————————————————————————
實現過程中需要一個邊表用來跑 Kruskal 。。
一個支持 del 操作的手寫鄰接表、。。。

    inline void del(int i){
        if (!prd[i]) prd[hd[aa] = suc[i]] = 0;
        else suc[prd[suc[i]] = prd[i]] = suc[i];
    }

    inline void dell(int i){
        del(i), del(i^1);
    }

    inline void add(int x, int y, int w){
        ww[m>>1] = w, prd[hd[x]] = m, suc[m] = hd[x], hd[x] = m, to[m++] = y;
        swap(x, y), prd[hd[x]] = m, suc[m] = hd[x], hd[x] = m, to[m++] = y;
    }

//if (!prd[i]) prd[hd[aa] = suc[i]] = 0;
(這個判斷之前都是寫的是 hd[aa] == i 。。。如果寫成 !prd[i] 的話。。則這一部必須把 prd [] = 0 也得維護掉。。。。
(。。用前者的話不維護也行。。總之敲的時候不多加小心的話是不行的呢、。)