重根技巧（rerooting technique）

一般的樹形動態規劃只生根一次，為每個節點計算它下方子樹的答案。但許多問題要的是「彷彿那個節點就是根」時，每個節點各自的答案——例如，對每個節點求到所有其他節點的距離之和，或把樹從該節點吊起時的高度。若從 n 個根各自重跑一次完整的 O(n) 樹形動態規劃，將花 O(n^2)。重根技巧能以總共 O(n) 得到全部 n 個根的答案，方法是先做一次生根的遍歷，再廉價地把根從一個節點滑到它的鄰居。

它分兩趟進行。第一趟，從任意根 r 出發的正常後序 DFS 填出 down[v]，即 v 子樹的貢獻（如同樸素樹形動態規劃）。第二趟，前序 DFS 把資訊往下推回：對每個節點 v 計算 up[v]，即 v 子樹「之外」的一切貢獻，也就是經由 v 的父節點往上走所能到達的那部分樹。節點 v 的完整答案於是是 down[v] 與 up[v] 的組合——從 v 看出去的整棵樹。訣竅在於高效地由 up[parent] 與父節點的其他子節點算出 up[child]：當你把根沿著邊（parent, child）移動時，child 把父節點那一側納為新的「外側」，並從父節點向下的總和裡去掉自己。要在每邊常數時間內做到這點，常需預先算好一個節點各子節點的前綴與後綴組合，以便快速排除任一個子節點。

兩趟都只觸碰每條邊常數次，所以整體是 O(n)——比從頭重根快了 n 倍。每當問題說「對每個頂點，計算依賴於樹其餘部分的 X」時，它就是標準工具。誠實的提醒是：重根需要那個合併運算支援移除或排除某一個子節點的貢獻（這樣你才能在不含你正要移入的子節點下重組父節點的值）；不易反轉的運算（例如純粹取最大值、而你又必須丟掉那個取到最大的子節點）就需要前綴／後綴或其他排除技巧，而非天真地相減。