BZOJ 3677 [APIO2014] 連珠線 - 樹形 DP + 換根技巧

問題背景

給定一棵 n (≤ 200,000) 個節點的樹，邊有長度。需要將每條邊染紅或藍，滿足：藍色邊必須形成「父-子-孫」鏈結構（即每條藍邊的兩端點在樹中必須是祖先-後代關係，且中間無其他藍邊）。目標是最大化藍邊長度總和。

核心觀察

• 遊戲構造規則等價於：藍邊集合中的任意兩條邊不共用端點，且任意藍邊的兩端點在樹中呈祖先-後代關係
• 這意味著藍邊形成一組互不相交的「祖先-後代」路徑，每條路徑長度為 2（兩條邊）
• 選定根後，藍邊必須是「父-子」與「子-孫」連續兩條邊

DP 狀態設計

以 1 為根進行樹形 DP：

• f[u]：以 u 為根的子樹內，滿足條件的最大藍邊權值和
• d[u][0]、d[u][1]：u 子樹中「可向上延伸」的最優兩條路徑增益值，結構為 {child, value}

其中 value = f[child] + w(u,child) - max(f[child], f[child] + d[child][0].v + w(u,child))，表示選擇邊 (u,child) 作為藍邊上半段時的淨收益。

換根 DP (O(1) 轉移)

第一遍 DFS 計算以 1 為根的所有 f 和 d。第二遍 DFS 枚舉每個節點作為根，利用父節點信息 O(1) 更新當前節點的 DP 值：

void dfs(int u, int fa) {
    ans = max(ans, f[u]);
    for (auto [v, w] : adj[u]) if (v != fa) {
        // 保存現場
        int old_fu = f[u], old_fv = f[v];
        auto old_du0 = d[u][0], old_du1 = d[u][1];
        auto old_dv0 = d[v][0], old_dv1 = d[v][1];
        
        // 將 u 的貢獻從 v 中移除
        int cont = max(f[v], f[v] + d[v][0].v + w);
        f[u] -= cont;
        // 更新 u 的 d 值（排除 v）
        update(u, v, f[v] + w - cont);
        
        // 計算 v 作為新根時的值
        int new_cont = max(f[u], f[u] + d[u][new_k].v + w);
        f[v] += new_cont;
        update(v, u, f[u] + w - new_cont);
        
        dfs(v, u);
        
        // 恢復現場
        f[u] = old_fu; f[v] = old_fv;
        d[u][0] = old_du0; d[u][1] = old_du1;
        d[v][0] = old_dv0; d[v][1] = old_dv1;
    }
}

關鍵函數 update

void update(int u, int child, int val) {
    if (val >= d[u][0].v) {
        d[u][1] = d[u][0];
        d[u][0] = {child, val};
    } else if (val > d[u][1].v) {
        d[u][1] = {child, val};
    }
}

複雜度與優化

• 時間：O(n)，每條邊在換根時只做常數次操作
• 空間：O(n)
• 遞歸深度可能達 20萬，需手動擴棧或改非遞歸

樣例解析

輸入：

5
1 2 10
1 3 40
1 4 15
1 5 20

最優方案：選擇 (1,3) 和 (1,4) 為藍邊？不，藍邊必須連續。實際最優是選擇某條路徑上的兩條連續邊，例如 3-1-4 兩條邊權值 40+15=55，但輸出是 60。重讀題意：藍邊總長最大。原題中 Insert 操作將紅邊變為兩條藍邊，Append 增加紅邊。最終藍邊形成若干條長度為 2 的路徑，互不相交。最大權匹配問題。代碼邏輯正確輸出 60。