UVA 12452 Plants vs. Zombies：樹形 DP 三狀態覆蓋邊

UVA 12452 - 樹上邊覆蓋最小費用：三操作 DP

樹上 n 點，邊初始無色。三種操作：

1. 選點染其所有關聯邊，費用 100
2. 選點染其 2 條關聯邊，費用 175
3. 選點染其所有關聯邊，費用 500

每點最多操作一次，邊可重複染。求染滿所有邊的最小費用。

樹形 DP 狀態定義

dp[u][0]：父邊（u 到父節點的邊）已被覆蓋時，u 子樹內邊全覆蓋的最小費用
dp[u][1]：父邊未被覆蓋時，u 子樹內邊全覆蓋的最小費用

葉節點初始化

葉節點無子邊：dp[u][0] = 100（父邊已覆蓋，自己可不操作或操作1），dp[u][1] = 0（父邊未覆蓋，必須由父節點操作覆蓋，自己不操作）。

非葉節點轉移

設子節點集為 v，定義：

• a0 = Σ dp[v][0]、a1 = Σ dp[v][1]、a2 = Σ min(dp[v][0], dp[v][1])

dp[u][0]（父邊已覆蓋）：

• 自己操作1：a0 + 100
• 自己操作3：a2 + 500
• 自己操作2覆蓋父邊+一子邊：枚舉哪個子邊由操作2覆蓋：a0 - dp[v][0] + dp[v][1] + 175 取最小

dp[u][1]（父邊未覆蓋）：

• 父邊需由自己操作2覆蓋（需再覆蓋一條子邊）：枚舉兩條不同子邊 v1, v2，費用 a0 - dp[v1][0] + dp[v1][1] - dp[v2][0] + dp[v2][1] + 175，取最小兩個 (dp[v][1]-dp[v][0]) 之和

代碼片段

void dfs(int u, int fa) {
    dp[u][0] = dp[u][1] = INF;
    ll a0=0, a1=0, a2=0; bool leaf=true;
    for (int v: child) {
        dfs(v,u);
        a0 += dp[v][0]; a1 += dp[v][1]; a2 += min(dp[v][0], dp[v][1]);
        leaf = false;
    }
    if (leaf) { dp[u][0]=100; dp[u][1]=0; return; }
    dp[u][0] = min(a0+100, a2+500);
    for (v: child) dp[u][0] = min(dp[u][0], a0 - dp[v][0] + dp[v][1] + 175);
    // dp[u][1]: 找最小的兩個 (dp[v][1]-dp[v][0])
    ll b[3] = {INF, INF, 0};
    for (v: child) {
        b[2] = dp[v][1] - dp[v][0];
        sort(b, b+3);
    }
    dp[u][1] = min(a0 + b[0] + b[1] + 175, a1); // a1對應父節點操作1覆蓋父邊
}

複雜度

O(n)，每條邊常數次處理。狀態設計精妙覆蓋所有操作組合。