POJ 1694 解題報告：樹形 DP 與貪心排序策略

題目背景

POJ 1694 為經典樹形動態規劃問題。給定一棵有根樹，每個葉節點代表一顆石頭，內部節點需合併子樹的石頭。合併規則：每次可合併兩堆，代價為較大堆的石頭數。求將所有石頭合併至根節點的最小總代價。

核心演算法

1. 遞歸結構：solve(u) 回傳子樹 u 合併完成後的石頭堆大小。
2. 葉節點基準：無子節點時回傳 1（單顆石頭）。
3. 貪心合併序：收集所有子樹回傳值至陣列 stone[]，由小到大排序。依序合併，維持 temp 為當前可容納的最大堆，若下一堆 ≤ temp 則 temp--，否則累加差值至 result 並更新 temp。

關鍵程式碼解析

int solve(int u) {
    if (tree[u].cnt == 0) return 1;          // 葉節點
    for (int j = 0; j < tree[u].cnt; ++j)
        stone[j] = solve(tree[u].leaf[j]);   // 遞歸處理子樹
    sort(stone, stone + tree[u].cnt);        // 關鍵：排序啟用貪心
    int result = stone[tree[u].cnt - 1];
    int temp = result - 1;
    for (int k = tree[u].cnt - 2; k >= 0; --k) {
        if (temp - stone[k] >= 0) temp--;
        else { result += stone[k] - temp; temp = stone[k] - 1; }
    }
    return result;
}

複雜度分析

• 時間：O(N log N)，主要來自各節點子樹結果排序。
• 空間：O(N)，遞歸堆疊與暫存陣列。

測試資料格式

輸入範例：
4 -3 0 0 1 3 0 0 0 -6 0
0 0 0 8 0
0 0 1 0 0
0 0 0 0 7
0 1 0 0 0
0 0 0

程式以 freopen 導向 in.txt/out.txt，適合離線測試。

心得總結

此題精髓在於「排序後由大合併至小」的貪心證明：優先處理大堆可最小化後續合併代價。樹形 DP 將問題分解為獨立子問題，配合排序策略，展現了演算法設計中「分治 + 貪心」的經典組合威力。