POJ 1639 度限制最小生成樹：動態規劃維護樹上最大邊迭代優化

問題描述

給定無向連通圖，節點 1 為「公園」，要求公園度數 ≤ k。求滿足度限制的最小生成樹總權重。

算法框架（王汀 IOI 論文）

1. 去掉根節點 1，剩餘圖生成最小生成森林（每棵樹最終需連回根）。
2. 每棵樹連根：選取該樹到根的最小邊，形成 m 度生成樹（m = 連通分量數）。
3. 迭代 k-m 次：每次選一條未用的根連接邊 (1, v)，形成環，刪除環上非根邊中權重最大者，度數 +1，總權重減少 maxEdge - w(1,v)。選擇使減少量最大的邊。

核心難點：動態維護「節點到根路徑上最大邊」

樹結構動態變化（刪邊加邊），需高效查詢 maxEdge[v] = v 到根路徑上最大邊權。
DP 遞推：以根為根 DFS，
maxEdge[v] = max(maxEdge[parent[v]], weight(v, parent[v]))
每次修改樹後，僅需從新加入節點 v 重新 DFS 更新其子樹，複雜度 O(子樹大小)。

關鍵數據結構

• use[u][v]：邊是否在當前樹中。
• pre[v]：樹中父節點。
• mx[v]：結構體 {u, v, w} 記錄 v 到根路徑上最大邊的兩端點與權重。
• link[i]：第 i 個連通分量連根的最小邊權及端點。

完整流程代碼片段

// 1. 去根建森林
vis[1]=1; dfs分連通塊;
for 每塊 prim建最小生成樹;

// 2. 連根形成 M 度樹
for 每塊找最小連根邊 link[塊], point[塊];
ans += Σ link[i]; use[1][point[i]]=1;

// 3. 迭代優化
for (deg = m; deg < k; deg++) {
    更新所有點 mx[] (從根 DFS);
    找未用連根邊 (1,v) 使 (mx[v].w - w(1,v)) 最大;
    若無增益 break;
    ans -= 增益;
    use[1][v]=1; use[mx[v].u][mx[v].v]=0; // 換邊
    從 v 重新 DFS 更新 mx[];
}

複雜度

Prim O(V log V + E) + k 次迭代 × O(V) 更新 = O(V log V + k·V)，V≤100、k≤V 完全足夠。