為何樹是動態規劃最好的朋友
上一篇導覽把動態規劃放在一條索引線上——一個區間。樹 是再上一階的形狀，而它原來同樣友善。樹是沒有環的連通圖，所以只要你挑任何一個節點當 根，其餘每個節點都恰有一個父節點，整個結構便向下垂掛成一層層嵌套的 子樹。這種嵌套正是動態規劃所要的 最佳子結構：一個節點的答案由它各孩子的答案組裝而成，而一個孩子的子樹永遠不會反過頭去碰它的父節點。沒有環去製造循環依賴，所以這些子問題形成了一個乾淨的偏序。
這就是為何 樹上動態規劃 是你會遇到最乾淨的設計樣式之一。拜訪節點最自然的方式，是從根出發的 深度優先搜尋：先下降到葉子，再讓答案往上冒回來。因為一個孩子在它的父節點需要之前就已被完全解掉，這個拜訪順序——後序，孩子先於父——自動就是一個合法的 求值順序。你不必像對區間動態規劃那樣親手設計填表的次序；遞迴本身就免費替你走好了依賴順序。
一趟搞定的子樹遞迴關係式
讓我們用一個經典問題把它具體化：樹上的 最大權重獨立集。每個節點帶一個權重，我們要選出一組總權重最大的節點，使得任兩個被選的節點都不相鄰（沒有被選的父子配對）。定義 狀態 是整門藝術的所在，而這裡它有兩個部分。對每個節點 v，我們保留兩個答案：down[v][0]，當 v 不被選時，v 的子樹內可得的最佳總和；以及 down[v][1]，當 v 被選時，v 的子樹內可得的最佳總和。同時保留這兩種可能，正是讓父節點能乾淨抉擇的關鍵。
現在 轉移 會自己從相鄰規則寫出來。若 v 不被選，每個孩子 c 都可自由選或不選，所以對每個孩子我們加上兩者中較好的那個。若 v 被選，則任何孩子都不可被選，所以對每個孩子我們被迫走「不選」那一支，並加上 v 自己的權重。寫成精簡形式：down[v][0] = 在各孩子 c 上對 max(down[c][0], down[c][1]) 求和；而 down[v][1] = weight(v) + 在各孩子 c 上對 down[c][0] 求和。整棵樹的答案是 max(down[root][0], down[root][1])。
function dfs(v, parent):
down[v][0] = 0
down[v][1] = weight[v]
for c in neighbors[v]:
if c == parent: continue # don't walk back up
dfs(c, v) # solve the child first
down[v][0] += max(down[c][0], down[c][1])
down[v][1] += down[c][0]
# answer = max(down[root][0], down[root][1])為何這是正確的？沿樹往上用 數學歸納法：在葉子處公式顯然成立（down[leaf][0]=0、down[leaf][1]=weight），而在內部節點處，「若」每個孩子的兩個答案都已最佳，那麼上面的 max／sum 就是該節點在它自己的二元抉擇下所能達到的最好結果。成本誠實且易讀：迴圈本體對每條父子邊跑一次，n 個節點的樹恰有 n-1 條邊，且每步是 O(1)，所以整個計算是 O(n) 時間、O(n) 空間。那個線性界，正是「沒有環」這個結構帶來的頭號獎賞。
一段小小的追蹤
拿一棵五節點的樹：根 A（權重 3）有孩子 B（權重 4）與 C（權重 1）；B 又有孩子 D（權重 2）與 E（權重 5）。葉子 D、E、C 先被解。對每個葉子，「不選」的答案是 0，「選」的答案是它自己的權重，所以 down[D]=(0,2)、down[E]=(0,5)、down[C]=(0,1)。目前還沒什麼意外——葉子的子樹就只是它自己。
- 節點 B 合併 D 與 E。down[B][0] = max(0,2) + max(0,5) = 2 + 5 = 7（跳過 B，兩個孩子皆可被選）。down[B][1] = weight(B) + down[D][0] + down[E][0] = 4 + 0 + 0 = 4（選 B，所以 D 與 E 被迫不選）。所以 down[B] = (7, 4)。
- 節點 A 合併 B 與 C。down[A][0] = max(7,4) + max(0,1) = 7 + 1 = 8。down[A][1] = weight(A) + down[B][0] + down[C][0] = 3 + 7 + 0 = 10。所以 down[A] = (8, 10)。
- 整棵樹的答案是 max(8, 10) = 10，由選 A、D、E（權重 3 + 2 + 5）達成，三者兩兩不相鄰。在這裡讀出「哪些」節點是容易的部分；一般情況下你藉由 重建解 來取回它，往下走並檢查每個 max 來自哪一支。
換根問題
這趟動態規劃回答的是「關於某個固定根」的問題，或是每個節點自己子樹的問題。但有一整族問題問的是不同的東西：對「每一個」節點 v，當 v 當根時答案是什麼——也就是一個從 v 的視角看見整棵樹、而非只看掛在它底下那部分的答案。一個乾淨的例子：對每個節點，求它到所有其他節點的距離總和。子樹動態規劃只看得到向下；從任何節點看，樹的大部分都在上方，穿過它的父節點。你也需要那塊來自「除我子樹以外的一切」的答案。
暴力的修法是把整趟 O(n) 的動態規劃，對每個根的選法重跑一次——n 次，總共 O(n^2)。這對幾千個節點還行，但超過之後就悄悄地沒指望了。換根法（有時叫「換根動態規劃」或「進出（in-and-out）」技巧）用第二趟深度優先搜尋，以總共 O(n) 取得每個節點的全樹答案。關鍵洞見：當你把根從節點 v 移到相鄰的節點 c 時，幾乎一切都不變。只有跨越單一條邊 v-c 的那層關係翻轉了。所以當你把根「滑」過去時，你應該能對每條邊用 O(1) 更新答案，而不是從頭重建。
第二趟如何運作
具體而言，對於距離總和問題，第一趟對每個節點 v 算出它的子樹大小 cnt[v]，以及 down[v] =「從 v 往下到它子樹內各節點」的距離總和。兩者都遵循簡單的後序遞迴關係式。被選根處的總答案，於是恰好就是 down[root]。整個挑戰，是把那單一個根的答案廉價地轉成每個節點的答案，而這正是「滑動根」這個恆等式發揮價值之處。
下面就是它的核心動作。設 ans[v] 是「從 v 到所有節點」的距離總和，而我們已知 ans[parent]。當我們把根從父節點跨那一條邊移到孩子 v 時，v 子樹內的每個節點都離 v 近了一步（共有 cnt[v] 個），而 v 子樹外的每個節點都遠了一步（共有 n - cnt[v] 個）。所以 ans[v] = ans[parent] - cnt[v] + (n - cnt[v])。這一個 O(1) 的更新，隨著第二趟深度優先搜尋把根從原本的根依序往外推到每個孩子，就把整棵樹的 ans 填滿。
兩趟，每趟 O(n)，所以總共 O(n)——和單根動態規劃同樣的線性成本，現在卻一次交出全部 n 個答案。這就是完整的 換根法：一趟由下而上總結每棵子樹，再一趟由上而下，重用父節點的完整答案、只就那一條改變的邊推理，來導出每個孩子的答案。同一副骨架能處理許多量——計數、最大值、模意義下的乘積、最長路徑——只要你能把「移除這個孩子的貢獻、加上其餘」表達成一個廉價、可逆的運算。
對「可逆」這個詞，有一個誠實的但書值得停下來想。距離更新之所以成立，是因為「減去一個孩子的貢獻」很容易——你只要用計數重算即可。但若合併步驟是「對各孩子取 max」，你就不能單純地「減去」你正換根穿過的那個孩子：那個 max 可能「本來就是」那個孩子。標準修法是在每個節點預先算好足夠的資訊，以回答「除這個孩子外、所有孩子中的最佳」——常是前綴與後綴 max，或乾脆是前兩大的值。換根確實是線性的，但只在每條邊的更新是 O(1) 時才成立；一個粗心的合併，會悄悄把分支數那個額外的因子塞回來。
界線、陷阱與誠實的適用範圍
把界線弄清楚。這裡的一切都建立在「樹真的是樹」之上——連通且無環。哪怕只多加一條邊，你就有了一個環，乾淨的父子偏序便崩塌，一個節點的子樹便能反過頭去影響它自己的祖先。一般圖上的動態規劃是難得多的遊戲；樹上動態規劃那份溫柔的線性，正是「沒有環」所配發的紅利。如果你的輸入是「一個剛好是樹的圖」，在信任以上任何一點之前，先確認它真的是樹（n 個節點、n-1 條邊、連通）。
兩個實務陷阱值得點名。其一，遞迴深度：一棵樹可以是 n 個節點的單一長鏈，所以遞迴式深度優先搜尋可能遞迴 n 層深，在大型輸入上讓呼叫堆疊溢位——這正是記憶化那篇所警告的、屬於真實機器的成本，也是在非常大的樹上要考慮用顯式堆疊或迭代式後序的理由。其二，「每條邊 O(1)」這個承諾，是對「合併」運算的承諾，而非定律；如果計算「除一個外的所有孩子」或那個換根更新偷偷花了 O(度數) 或 O(log n)，你的總成本就不再是線性。在宣稱 O(n) 之前，永遠先檢查每條邊的工作量是否真的是常數。
最後，誠實看待適用範圍。換根用一趟額外的工作，為你買來「每個節點處的答案」——相對於把動態規劃重跑 n 次，這是貨真價實的漸進勝利。但若你永遠只需要某個固定根處的答案，光第一趟就夠了，第二趟是白費的力氣；換根並不是一個你總該套用的免費升級。一如本輪始終如此，真正的功夫在於辨認問題的「形狀」——一個根還是所有根、只向下還是整棵樹——再去拿匹配的工具。下一篇導覽會把同樣那份「小而可重用的狀態、謹慎的轉移」直覺，帶進一個非常不同的場域：編碼成位元遮罩的子集。