换根法（Rerooting）算法详解

1. 什么是换根法换根法Rerooting是一种在树形数据结构通常是树或图上解决动态规划问题的算法技巧。其核心思想是先以树中任意一个节点为根进行一次深度优先搜索DFS计算出以该节点为根的子树相关的答案然后通过第二次 DFS利用已计算出的信息高效地将根节点“换”到其他节点并计算出以新节点为根时的答案。这种方法避免了为每个节点作为根都进行一次完整的 O(n) 遍历从而将总时间复杂度从 O(n²) 优化到 O(n)。2. 算法思想与步骤2.1 第一次 DFS预处理自底向上任选一个节点通常为节点 0 或 1作为初始根进行一次后序遍历Post-order Traversal。计算每个节点只考虑其子树时的状态值。例如子树大小、子树节点权值和、子树中最长路径等。将子节点的信息“贡献”给父节点完成自底向上的信息聚合。这一步结束后我们得到了以初始根节点为根时所有节点的“子树信息”。2.2 第二次 DFS换根自顶向下从初始根节点开始进行前序遍历Pre-order Traversal。当从父节点u遍历到子节点v时我们已知以u为根时整棵树的信息。现在要将根从u“换”到v。这意味着节点v的子树相对于原根保持不变。节点u及其除v以外的其他子树将变成节点v的一棵新子树。利用第一次 DFS 计算出的“子树信息”我们可以 O(1) 或 O(子节点数) 地计算出以v为根时所需的信息。将计算出的以v为根的答案记录下来然后递归地对v的子节点进行同样的换根操作。3. 经典应用场景求树中每个节点到其他所有节点的距离之和LeetCode 310. Minimum Height Trees 的变体或直接求“距离和”。求树中以每个节点为根时的子树大小/权值和。求树中以每个节点为根时的最长路径树的直径。求树中以每个节点为根时满足某种条件如颜色、奇偶性的节点个数。在加权树上求每个节点到其他节点的最大/最小代价。4. 代码模板C#include vector #include functional using namespace std; /** 换根法通用模板框架C 假设问题求以每个节点为根时其子树节点值的和节点值默认为1即求子树大小。 */ vectorint rerooting(int n, vectorvectorint edges) { // 建图 vectorvectorint graph(n); for (auto e : edges) { int u e[0], v e[1]; graph[u].push_back(v); graph[v].push_back(u); } // 第一次DFS后序遍历计算子树信息 dp_sub vectorint dp_sub(n, 0); // dp_sub[u] 表示以u为根的子树节点和 functionvoid(int, int) dfs1 [](int u, int parent) { dp_sub[u] 1; // 节点自身 for (int v : graph[u]) { if (v parent) continue; dfs1(v, u); dp_sub[u] dp_sub[v]; // 累加子树的贡献 } }; dfs1(0, -1); // 假设以0为初始根 // 第二次DFS前序遍历进行换根计算最终答案 ans vectorint ans(n, 0); // ans[u] 表示以u为根时整棵树的节点和 ans[0] dp_sub[0]; // 初始根的结果就是其子树和即整棵树 functionvoid(int, int) dfs2 [](int u, int parent) { for (int v : graph[u]) { if (v parent) continue; // 将根从 u 换到 v // 1. 从 u 的贡献中移除 v 的子树贡献 // 2. 将 u及其剩余部分作为 v 的新子树贡献加给 v // 对于“子树节点和”问题 // ans[v] dp_sub[v] (ans[u] - dp_sub[v]) // 化简后ans[v] ans[u] // 但通用情况需要更复杂的转移这里展示框架 ans[v] dp_sub[v] (ans[u] - dp_sub[v]); dfs2(v, u); } }; dfs2(0, -1); return ans; } // 示例一棵4个节点的链 0-1-2-3 int main() { int n 4; vectorvectorint edges {{0,1},{1,2},{2,3}}; vectorint result rerooting(n, edges); // 输出每个节点为根时的子树节点和实际上对于链就是节点数4 for (int val : result) { printf(%d , val); } return 0; }5. 关键点与注意事项状态定义明确第一次 DFS 要计算的“子树信息”是什么以及如何从子节点转移到父节点。换根转移方程这是最核心的部分。需要推导出当根从父节点u换到子节点v时如何利用已知的dp_sub和ans[u]快速计算出ans[v]。初始化注意初始根节点答案的初始化。避免重复计算在第二次 DFS 中当计算子节点v的答案时要确保使用的父节点u的答案是最新的即已经完成了换根到u的计算。复杂度两次 DFS 都是 O(n)总时间复杂度 O(n)空间复杂度 O(n)。6. 实战例题解析LeetCode 310. Minimum Height Trees问题可以转化为对于无向图树求以每个节点为根时的树高然后找出最小高度对应的根节点集合。使用换根法第一次 DFS 计算每个节点向下的最大高度和次大高度用于换根时当最深的路径经过当前子节点时需要使用次大高度。第二次 DFS 进行换根计算每个节点向上的高度即从父节点方向来的最长路径然后结合向下的高度得到以该节点为根时的总高度。此处可展开详细代码限于篇幅省略7. 总结换根法是一种非常高效的树形 DP 优化技巧将“为每个根计算答案”的问题从 O(n²) 优化到 O(n)。掌握其核心的两次 DFS 流程自底向上预处理 自顶向下换根以及状态转移方程的推导是解决此类问题的关键。在 LeetCode、Codeforces 等算法竞赛中换根法是解决树形问题的必备高级技能之一。