1. 从一个树形问题说起为什么需要“换根”在算法竞赛和面试中树形动态规划Tree DP是绕不开的经典题型。我们通常能熟练地处理以某个固定节点为根的子树问题比如计算子树大小、子树最大权值和等。这类问题有一个共同点我们默认了一个“根”节点所有状态转移都从这个根向下从父节点到子节点进行。但现实或者说题目往往更复杂。考虑这样一个问题给定一棵带权树对于树中的每一个节点计算以该节点为整棵树的根时所有节点到它的距离之和。换句话说我们需要求出每个节点的“距离和”。如果你尝试用一次普通的树形DP来解决会发现非常棘手。因为一次DFS只能固定一个根要计算所有节点难道要对每个节点都做一次O(N)的DFS吗那总复杂度就是O(N²)对于节点数上万的数据规模这显然是不可接受的。这就是“换根法”或称换根DP要解决的核心痛点在树形结构上当我们需要计算以每个节点为根时的某个全局属性并且这些属性之间存在可推导的递推关系时通过一次或两次DFS高效地计算出所有答案。它的思想非常巧妙我们先任选一个节点比如1号节点作为初始根进行一次DFS计算出以该节点为根时的答案以及一些必要的子树信息。然后我们再进行一次DFS“换根”的过程利用已知的根节点答案和子树信息推导出它的子节点作为新根时的答案。通过这种方式我们就能从已知的一个答案“扩散”出所有节点的答案。理解换根法关键在于抓住两个核心一是状态的重新定义与转移二是父子关系互换时的增量计算。接下来我们从一个最经典的例题入手拆解其完整思路。2. 经典例题拆解所有节点到根节点的距离和我们以最经典的问题作为切入点给定一棵N个节点的无根树每条边有一个长度权值。对于每个节点u计算dp[u]表示所有节点到u的距离之和。即dp[u] sum(dist(v, u))其中v取遍所有节点。2.1 第一次DFS预处理子树信息我们首先任意选取一个节点作为根这里选节点1将其转化为有根树。 这次DFS的目标有两个计算以每个节点u为根的子树大小size[u]包括u自身。计算以节点1为根的答案dp[1]即所有节点到根节点1的距离和。定义状态size[u]: 以u为根的子树中的节点总数。dp[u]: 在当前根节点1的视角下u的子树中所有节点到u的距离之和。注意这个dp[u]还不是我们最终要求的全局dp[u]它仅代表子树内部的距离和。第一次DFS的转移方程自底向上后序遍历初始化size[u] 1自身。对于u的每个子节点v边权为w递归处理子节点v得到size[v]和dp[v]子树v内部的距离和。size[u] size[v]dp[u] dp[v] size[v] * w解释dp[v]是子树v中所有节点到v的距离和。现在这些节点要走到u需要多走一条边u-v权值为w。子树v中共有size[v]个节点所以总距离额外增加size[v] * w。当DFS返回到根节点1时我们得到了dp[1]。此时的dp[1]恰好就是所有节点到节点1的距离和因为节点1的“子树”就是整棵树。我们记这个值为ans[1]即ans[1] dp[1]。同时我们也得到了所有节点的size[u]。size[u]是一个非常重要的信息它将在换根时起到关键作用。2.2 第二次DFS换根推导与答案传递现在我们知道了以节点1为根的答案ans[1]。假设我们知道了节点u的答案ans[u]如何推导出其子节点v的答案ans[v]呢这是换根法最精妙的部分。我们把根从u“换”到v树的形态发生了变化。在u为根时树被分为两部分以v为根的子树称为“子树部分”和剩下的其他部分称为“上方部分”。当根变成v后对于原“子树部分”即v的子树这部分节点原来需要走到u现在根变成了v它们需要走的路程变短了。具体来说对于这部分中的任意节点到新根v的距离比到旧根u的距离少了边(u, v)的权值w。这部分节点共有size[v]个所以总距离减少size[v] * w。对于原“上方部分”除v子树外的所有节点共N - size[v]个这部分节点原来需要走到u现在根变成了v它们需要走的路程变长了。因为它们需要先走到u再经过边(u, v)才能到v。所以每个节点到新根的距离比到旧根的距离多了权值w。总距离增加(N - size[v]) * w。综合以上两点我们可以得到换根转移方程ans[v] ans[u] - size[v] * w (N - size[v]) * w化简后ans[v] ans[u] (N - 2 * size[v]) * w这个公式的物理意义非常清晰从u换根到v总距离的变化量是(N - 2 * size[v]) * w。如果size[v] N/2即v的子树节点数超过一半那么(N - 2*size[v])为负总距离减少符合直觉根更靠近节点密集区。如果size[v] N/2总距离增加。如果size[v] N/2总距离不变。第二次DFS先序遍历就从已知ans[1]的根节点1开始对于每个子节点v利用上述公式计算ans[v]然后递归地对v的子节点继续进行换根推导。注意在第二次DFS中我们是在一棵以1为根的有根树上进行遍历利用父子关系和预处理好的size数组进行转移。ans[u]代表的是以u为整棵树的根时的答案。2.3 代码实现与注释#include iostream #include vector using namespace std; using ll long long; const int MAXN 1e5 5; struct Edge { int to, w; }; vectorEdge graph[MAXN]; ll size[MAXN]; // 子树大小 ll dp[MAXN]; // 第一次DFS用的dp表示子树内节点到当前根的距离和 ll ans[MAXN]; // 最终答案表示以每个节点为整棵树根时的距离和 int N; // 第一次DFS计算size和dp以u为根的子树信息 void dfs1(int u, int fa) { size[u] 1; dp[u] 0; for (auto [v, w] : graph[u]) { if (v fa) continue; dfs1(v, u); size[u] size[v]; dp[u] dp[v] size[v] * w; // 关键递推 } } // 第二次DFS换根计算ans void dfs2(int u, int fa) { for (auto [v, w] : graph[u]) { if (v fa) continue; // 核心换根公式 ans[v] ans[u] (N - 2 * size[v]) * w; dfs2(v, u); } } int main() { cin N; for (int i 1; i N; i) { int u, v, w; cin u v w; graph[u].push_back({v, w}); graph[v].push_back({u, w}); } // 任选根节点1 dfs1(1, 0); // 此时dp[1]就是以1为根的答案 ans[1] dp[1]; dfs2(1, 0); for (int i 1; i N; i) { cout ans[i] endl; } return 0; }复杂度分析两次DFS每个节点和每条边都被访问常数次时间复杂度为 O(N)。空间复杂度 O(N)。这相比暴力 O(N²) 是巨大的优化。3. 换根法的通用框架与状态设计通过上面的例子我们可以抽象出换根法解决问题的通用步骤和状态设计思路。3.1 标准解题流程定根与第一次DFS预处理任选一个节点作为初始根通常选1。进行一次自底向上的DFS后序。目标计算出以每个节点u为根的子树的相关信息。这些信息通常包括两部分子树贡献 (down[u])完全位于u的子树内的节点对u的答案贡献。例如上例中的dp[u]。子树属性 (size[u],maxVal[u]等)描述子树本身状态的量如节点数、最大值等。这些属性可能用于计算“上方部分”的贡献。第二次DFS换根推导进行一次自顶向下的DFS先序。目标已知父节点u作为整棵树根时的答案ans[u]推导出子节点v的答案ans[v]。核心分类讨论贡献来源。当根从u换到v对于新根v的答案其贡献来源可以重新划分为来自v的子树的贡献这部分在第一次DFS中已经以v为根计算过了即down[v]但需要注意此时的down[v]是在以u为整棵树根的视角下计算的它本身就是v子树内部到v的距离和无需改变。来自“上方部分”除v子树外的贡献这部分是换根计算的关键。我们需要利用已知的ans[u]和v的子树信息推导出“上方部分”节点到新根v的贡献。3.2 状态定义与转移设计心法设计状态是换根DP的核心难点。通常需要定义两类状态down[u]表示在以u的父节点为整棵树根的视角下u的子树对u的贡献。这是一个“局部”状态在第一次DFS中容易计算。up[u]表示在以u的父节点为整棵树根的视角下除u的子树外的所有部分即“上方部分”对u的贡献。这个状态有时显式定义有时隐含在换根公式中。ans[u]最终答案ans[u] combine(down[u], up[u])。在第二次DFS中我们就是通过ans[fa]来推导up[u]进而得到ans[u]。通用转移思路在第二次DFS中对于边(u-v, w)已知ans[u]包含了全树对u的贡献。要求ans[v]。思考ans[u]的贡献由v的子树部分 其他部分 构成。那么“其他部分”即u的答案中除去v子树贡献的部分对v的贡献就是up[v]需要计算的核心。通常up[v] combine(up[u], down[u] without subtree_v)再根据边权w进行调整。实操心得很多复杂的换根DP问题难点就在于如何正确地组合up[u]和down[u]中除去子节点v贡献的部分。一个常见的技巧是在第一次DFS时不仅计算down[u]还记录下最大值和次大值或对应的子节点编号。这样在第二次DFS计算up[v]时如果v是u取得down[u]最大值的子节点那么up[v]就应该用u的次大值来参与计算以确保信息来自“其他部分”。4. 进阶应用与变形分析掌握了基础的距离和问题我们来看几个变种理解如何灵活运用换根框架。4.1 例题树的直径所有节点最远距离问题对于一棵带权树求出每个节点到其他所有节点的最远距离。分析这是一个典型的树形DP问题但需要换根。对于每个节点u其最远距离可能来自两个方向向下走进入u的某个子树即down方向的最长路径。向上走经过父节点可能进入父节点的其他子树或者继续向上即up方向。状态设计down1[u],down2[u]记录以u为根的子树中从u出发向下的最长和次长路径长度并记录最长路径来自哪个子节点son[u]。这是第一次DFS可以求出的。up[u]记录从u出发向父节点方向走能获得的最长路径长度。这是第二次DFS换根要求解的。最终答案ans[u] max(down1[u], up[u])。第一次DFS求down1,down2,son。 对于节点u遍历子节点v边权w。计算len down1[v] w。如果len down1[u]则down2[u] down1[u],down1[u] len,son[u] v。否则如果len down2[u]则down2[u] len。第二次DFS换根求up。 对于节点u和其子节点v边权w。我们要计算up[v]。如果v就是u的最长子节点 (v son[u])那么从v向上走经过u之后最远的路径可能是up[u] w继续向上或者是down2[u] w走到u后进入u的次长子树。所以up[v] max(up[u], down2[u]) w。如果v不是u的最长子节点那么从v向上走经过u之后最远的路径可能是up[u] w或者是down1[u] w走到u后进入u的最长子树。所以up[v] max(up[u], down1[u]) w。通过这种方式我们利用down1,down2和son确保了up[v]的计算不会错误地包含v自身的子树贡献。4.2 例题树的最大权值连通块K步换根问题简化描述树上每个节点有正负权值。定义连通块的权值为块内节点权值和。对于每个节点u求以u为根时权值最大的连通块连通块必须包含根u且是连通的。这本质是求每个节点的“子树”最大和但这里的“子树”是以u为根时的整棵树需要换根。分析这是一个带权值的换根问题。定义f[u]为在以u为根的子树中选择包含u的连通块的最大权值和类似最大子段和但必须在树上且包含根。 第一次DFS可以求出每个节点向下的f[u]f[u] val[u] sum(max(0, f[v]))其中v是u的子节点。因为负数的子树我们不选。第二次DFS换根。设ans[u]是以u为整棵树根时的答案。已知ans[u]如何求子节点v的ans[v]ans[v]由两部分组成v向下的部分即f[v]和v向上的部分。v向上的部分可以看作是从u出发不经过v子树能获得的最大贡献。这其实就是ans[u]减去v子树对u的贡献如果贡献为正。即up_part ans[u] - max(0, f[v])。那么ans[v] f[v] max(0, up_part)。注意up_part可能为负为负则不选。这个例子展示了如何将“最大连续和”的思想与树形结构、换根操作结合。关键在于理解换根后子节点v的“上方部分”贡献可以通过父节点u的全局答案减去v子树的贡献来推导。4.3 边界条件与初始化陷阱换根法看似公式简洁但边界条件和初始化极易出错。根节点的初始化第一次DFS后根节点的ans[root]通常就等于down[root]。但up[root]需要谨慎初始化。对于距离问题up[root]通常为0因为根没有父节点。但对于像“最大距离”问题up[root]可能初始化为一个极小值如 -INF表示向上没有路径。叶子节点的处理在第二次DFS的转移公式中要确保公式对叶子节点也有效。例如在距离和问题中叶子节点的size[v]为1公式ans[v] ans[u] (N - 2) * w仍然成立。负权边与零权边上述公式对边权w没有正负要求。但如果问题涉及最大值、最小值如最大路径和并且允许负权边那么初始化down数组时就不能简单初始化为0而可能初始化为负无穷并且状态转移中的max操作要小心处理。多子树信息维护当转移需要用到“除某个子树外”的信息时如求次大值务必在第一次DFS中就维护好。这是避免O(N²)复杂度的关键。常见的维护方法是记录最大值、次大值以及最大值来自哪个子节点。踩坑记录我曾在一个比赛中遇到一道题需要计算每个节点到所有关键点的最大距离。我使用了换根法但在维护up值时只考虑了父节点u的up[u]和down1[u]忘记了如果v是u取得down1[u]的子节点那么应该用down2[u]来更新up[v]。这个错误导致在链式数据下答案错误。调试了很久才发现是状态转移的分类讨论漏了一种情况。教训是设计换根转移时必须画图清晰地区分当前子节点是否为父节点获取关键信息的来源节点。5. 从换根DP到更一般的“二次扫描”思想换根法本质上是一种“二次扫描”思想在树形结构上的应用。其核心是第一次扫描自底向上收集子树信息得到以每个节点为根的局部视图。第二次扫描自顶向下利用已知的全局信息和父子关系将局部视图整合或转化为其他节点为根的全局视图。这种思想可以推广到一些非标准的“换根”场景。例如无根树定根后的属性计算很多树形问题本身不需要换根但第一次DFS自底向上计算后可能还需要一次自顶向下的DFS来传递一些诸如“父节点对子节点的限制信息”等。删除一条边后的统计问题考虑删除树中的一条边(u, v)树被分成两棵子树。需要快速知道两棵子树的大小、权值和等信息。这可以转化为以u为根v的子树信息就是size[v]而以v为根u的子树信息就是N - size[v]如果最初以u为根进行计算。这其实就是一次隐性的“换根”思考。理解“二次扫描”的精髓就能在遇到新的树形统计问题时判断能否通过一次预处理一次推导来高效求解从而避免对每个节点进行独立计算的暴力做法。6. 总结与实战建议换根DP是一种非常有力的工具它将O(N²)的问题优化到O(N)。要掌握它建议遵循以下路径理解经典模型彻底吃透“所有节点距离和”这个例题。理解size数组的作用以及ans[v] ans[u] (N - 2*size[v]) * w这个公式的每一个变量的含义和推导过程。这是所有换根问题的基础。掌握状态设计范式遇到新问题先想清楚最终答案ans[u]是什么它能否分解为down[u]子树贡献和up[u]上方贡献down[u]如何通过一次DFS求出已知ans[u]即down[u]和up[u]的组合如何推导出子节点v的up[v]和ans[v]画图分类讨论是必须的。注意细节与边界多考虑叶子节点、根节点、负权、零权等边界情况。对于需要维护最大值/次大值的问题确保在第一次DFS时就正确维护。从简单到复杂练习基础距离和、距离最大值树的直径。进阶带点权的最大连通块和、树上每个点的最长路径需维护前三长的边、特定节点如所有关键点的统计信息。挑战结合其他算法如换根DP优化树上背包问题、与数位DP结合等。最后再分享一个调试小技巧写完换根DP代码后可以用小数据N10进行暴力对拍。暴力算法就是对每个节点作为根进行一遍DFS计算答案。虽然慢但能确保正确性。用随机生成的树结构和小权值进行大量测试能快速发现状态转移公式中的错误。