POJ 1155 & 2468 樹形 DP 專題詳解

題目一：POJ 1155 TELE（信號傳輸最大用戶數）

問題描述

樹形網絡，根為發射台，葉為用戶。每條邊有傳輸成本。用戶願意支付一定費用。選擇服務哪些用戶，使總收入 ≥ 總成本，且服務用戶數最大。N ≤ 3000。

樹形 DP 設計

f[u][k]：以 u 為根的子樹中，服務 k 個用戶的最大利潤（收入-成本）。
葉節點（用戶）：f[u][1] = pay[u]，f[u][0] = 0。
內部節點：合併子樹。對每個子樹 v，邊成本 c：

for (int k = size_u; k >= 0; k--)
    for (int j = 0; j <= size_v; j++)
        f[u][k+j] = max(f[u][k+j], f[u][k] + f[v][j] - c);

代碼要點

• 邊表存圖，遞歸 DFS。
• 初始化 f[u][*] = -INF。
• 合併時倒序枚舉 k 防止重複使用。
• 最終從 f[1][m] 遞減找第一個 ≥ 0 的 m。

題目二：POJ 2468 Apple Tree（K 步內最大蘋果數）

問題描述

樹上每節點有蘋果數。從節點 1 出發，最多走 K 步（每條邊 1 步），可重複經過節點但蘋果只能吃一次。求最大蘋果數。N ≤ 100, K ≤ 200。

三維 DP 狀態

f[u][k][0]：在 u 子樹內走 k 步，**必須返回 u** 的最大蘋果數。
f[u][k][1]：在 u 子樹內走 k 步，**可不返回 u**（最終停在子樹中）的最大蘋果數。

轉移方程（合併子樹 v，邊長 1）

對當前 u 已合併部分步數 run，分配給 v 步數 down：

• 0→0（去 v 並回）：f[u][run+2][0] = max(..., f[u][run-down][0] + f[v][down][0])
• 0→1（去 v 不回，u 部分需回）：f[u][run+1][1] = max(..., f[u][run-down][0] + f[v][down][1])
• 1→1（u 部分不回，去 v 回來）：f[u][run+2][1] = max(..., f[u][run-down][1] + f[v][down][0])

代碼要點

• 初始化：f[u][*][0] = f[u][*][1] = apple[u]。
• 遞歸合併，步數倒序枚舉。
• 答案：f[1][K][1]。

樹形 DP 核心模式總結

1. 狀態定義：以子樹為單位，包含「選擇數量/步數」與「是否返回根」等維度。
2. 合併順序：DFS 後序，子樹合併到父節點。
3. 背包式合併：雙重循環分配資源（名額/步數），倒序防重複。
4. 邊權處理：在合併時扣除/增加邊成本。

總結

兩道題展示了樹形 DP 的兩大經典模型：「選擇子樹項目」背包（POJ 1155）與 「樹上行走步數」三維 DP（POJ 2468）。掌握狀態設計與合併邏輯是關鍵。