樹形動態規劃（tree DP）

樹是一種沒有環的分枝結構——家族樹、檔案系統、沒有迴路的道路網。許多關於樹的問題帶有優美的遞迴味道：一個節點的答案只取決於它子節點的答案，而那又取決於它們的子節點，如此一路下到葉子。樹形動態規劃正是利用這點。你不再用陣列中的位置來索引表格，而是用節點來索引，且一個節點的答案是由懸掛在它下方的子樹中已算好的答案組裝而成。

做法是：任選一處生根，再以「每個子節點都在其父節點之前完成」的順序處理節點——也就是後序遍歷（一種在回返時合併結果的深度優先搜尋）。定義 dp[v] 為以節點 v 為根的子樹的最佳答案，並寫出由 v 的子節點 dp 值建出 dp[v] 的轉移。常常每個節點需要兩個狀態來處理「v 取或不取」的選擇。經典範例是樹上的最大獨立集（沒有兩點相鄰的最大節點集）：令 dp[v][0] 為「不取 v」時 v 子樹的最佳值，dp[v][1] 為「取 v」時的最佳值。則 dp[v][1] = 1 + 在子節點 c 上對 dp[c][0] 求和（若取 v，就不能取它的子節點），而 dp[v][0] = 在子節點 c 上對 max(dp[c][0], dp[c][1]) 求和（若略過 v，每個子節點都可自由取或不取）。答案是 max(dp[root][0], dp[root][1])。

由於每個節點與每條親子邊都只被觸碰常數次，樹形動態規劃通常以 O(n) 時間執行（狀態較豐富時為 O(n 乘以每節點狀態工作量）），便宜得很。凡是出現樹的地方它都登場：子樹大小、最長路徑、計數匹配、在相鄰規則下選取節點子集。它天然的限制是遞迴必須是局部的——dp[v] 要能僅由子節點表出。當你還需要每個節點「向外」穿過父節點的答案（而不只是向下進入子樹）時，單一生根就不夠，你便要用上重根技巧。