樹形DP解決新年獎金分配問題：最大匹配優化

問題建模：樹上最大匹配

公司层级結構是一棵樹（根節點1為Bill Hates）。每個程序員要么：

• 獲得上級發放的獎金
• 發放獎金給一個下級
• 不參與獎金分配

約束： 不能同時獲得和發放；一個人最多發放給一個下級。
目標： 最大化獲得獎金的總人數（每人1000美元）。

樹形 DP 狀態定義

dp[u][0] : 節點 u 不與父節點匹配時，子樹內最大匹配數
dp[u][1] : 節點 u 與父節點匹配時，子樹內最大匹配數

狀態轉移方程

• dp[u][1]：u 已與父匹配，不能再與任何孩子匹配
  dp[u][1] = Σ dp[v][0] （v 為 u 的所有孩子）
• dp[u][0]：u 不與父匹配，兩種情況取最大
  1. u 不與任何孩子匹配：Σ dp[v][0]（等同於 dp[u][1]）
  2. u 與某個孩子 v 匹配：1 + dp[v][1] + Σ_{w≠v} dp[w][0]
  取所有孩子中最大增益：
  dp[u][0] = max( dp[u][1], max_{v} (1 + dp[v][1] - dp[v][0] + dp[u][1]) )

路徑回溯輸出方案

void dfs_print(int u, int matched_with_parent) {
    if (matched_with_parent) {
        // u 與父匹配，所有孩子狀態為 0
        for (v : children[u]) dfs_print(v, 0);
    } else {
        // 找出實現 dp[u][0] 的最優決策
        int best_gain = 0, best_v = -1;
        for (v : children[u]) {
            int gain = 1 + dp[v][1] - dp[v][0];
            if (gain > best_gain) best_gain = gain, best_v = v;
        }
        if (best_v == -1) {
            // u 不匹配任何孩子
            for (v : children[u]) dfs_print(v, 0);
        } else {
            // u 與 best_v 匹配
            printf("%d ", best_v);  // 輸出獲得獎金的孩子
            dfs_print(best_v, 1);   // best_v 與父匹配
            for (v : children[u]) if (v != best_v)
                dfs_print(v, 0);
        }
    }
}

複雜度分析

• N ≤ 500,000，O(N) 時間，O(N) 空間
• 遞歸深度可能達 N，需改用迭代/显式棧或增大棧限制
• 輸入保證父節點編號 < 子節點編號，可按序 1..N 直接構建鄰接表

樣例驗證

輸入：
4
1 1 2    // 2,3的父是1；4的父是2
樹結構：1→{2,3}, 2→{4}

輸出：
2000
3 4
解釋：1發給2，3發給4（或2發給4，3不參與），共2人獲獎

關鍵實現細節

1. 內存優化： 用鄰接表 vector children[N+1]，避免邊數組
2. 非遞歸後序： 拓撲序/反序遍歷節點計算 dp，避免棧溢出
3. 輸出排序： 回溯收集結果後排序輸出