樹形 DP 經典題：新年獎金分配 (最大匹配) — 狀態定義、轉移與路徑恢復

樹形 DP 經典題：新年獎金分配 (最大匹配)

來源：POJ / ZOJ / Tsinghua OJ — New Year Bonus Grant
模型：給定一棵根樹（N ≤ 500,000），每個節點至多與父節點或一個子節點匹配，求最大匹配邊數並輸出匹配節點編號。

核心觀察

• 二分圖匹配 O(N√N) 或網絡流不可行（N 太大）。
• 樹上無環 → 樹形 DP 線性時間可解。
• 每個節點三種狀態：與父匹配、與某子匹配、不匹配。

狀態定義

• dp[u][0]：節點 u 不與父節點匹配時，子樹內最大匹配數。
• dp[u][1]：節點 u 與父節點匹配時，子樹內最大匹配數（此時 u 不能再與任何子節點匹配）。

轉移方程

// 1. u 與父匹配 → 所有子 v 必須取 dp[v][0]
dp[u][1] = Σ dp[v][0]          (v 遍歷 u 的所有孩子)

// 2. u 不與父匹配 → 兩種子情況取最大
//    (a) u 也不與任何子匹配
dp[u][0] = dp[u][1]            // 基礎值 = Σ dp[v][0]

//    (b) u 與某個具體子 v 匹配
//        邊 (u,v) 貢獻 1，v 必須取 dp[v][1]，其他子 w≠v 取 dp[w][0]
//        增益 = 1 + dp[v][1] - dp[v][0]
//    取所有子中的最大增益（若增益>0）
dp[u][0] = max( dp[u][0],  dp[u][1] + max(0, 1 + dp[v][1] - dp[v][0]) )

路徑恢復（輸出匹配節點）

自根向下 DFS，根據父節點決策決定當前節點狀態：

void dfs_output(int u, bool parent_matched) {
    if (parent_matched) {
        // 父已與 u 匹配 → u 狀態=1，不可再匹配子
        for (v: children[u]) dfs_output(v, false);
        return;
    }
    // 父未與 u 匹配 → u 狀態=0
    // 找出是否有子 v 使 dp[u][0] == dp[u][1] + 1 + dp[v][1] - dp[v][0]
    int best_v = -1;
    for (v: children[u]) {
        if (dp[u][0] == dp[u][1] + 1 + dp[v][1] - dp[v][0]) {
            best_v = v; break;
        }
    }
    if (best_v != -1) {
        // u 與 best_v 匹配 → 輸出 u, best_v
        ans.push_back(u); ans.push_back(best_v);
        dfs_output(best_v, true);          // best_v 狀態=1
        for (v: children[u]) if (v != best_v) dfs_output(v, false);
    } else {
        // u 不匹配任何子
        for (v: children[u]) dfs_output(v, false);
    }
}

複雜度分析

工程落地提示

1. 輸入優化：N=5e5，用 scanf/fastio，鄰接表用 vector 或靜態數組 head/next/to。
2. 遞歸棧：Linux 默認 8MB，500000 * 32B ≈ 16MB 可能爆棧。
   方案：ulimit -s unlimited、編譯加 -Wl,--stack,268435456 (Windows)、或手寫迭代後序遍歷。
3. 輸出升序：題目要求升序輸出，收集後 sort(ans.begin(), ans.end())。
4. 金額換算：每匹配邊 1000 美元，答案 = dp[1][0] * 1000。

樣例演示

輸入:
4
1 1 2        // 2的父=1, 3的父=1, 4的父=2
樹: 1→{2,3}, 2→{4}

DP過程:
葉子 3,4: dp[3][0]=0, dp[3][1]=0; dp[4][0]=0, dp[4][1]=0
節點 2: dp[2][1]=dp[4][0]=0; dp[2][0]=max(0, 0+1+0-0)=1 (匹配 2-4)
節點 1: dp[1][1]=dp[2][0]+dp[3][0]=1; dp[1][0]=max(1, 1+1+dp[2][1]-dp[2][0])=max(1,1+1+0-1)=1
根無父 → 取 dp[1][0]=1 → 匹配數=1 → 金額=2000
匹配點: 3,4 (或 2,4 視具體實現，樣例輸出 3 4)

小結

樹形 DP 解決「樹上最大匹配」是教科書級應用：狀態拆分「與父匹配/不匹配」，轉移中引入「增益」概念選最佳孩子匹配。N=5e5 要求 O(N) 時空與棧安全，工程上需注意輸入輸出優化與遞歸深度。此題完美展示了「狀態機 + 貪心增益」在樹上 DP 的威力。