换根 DP 这个模型我最早是在一场模拟赛里被狠狠折磨过一次。题目给出一棵 N 个节点的无根树N 开到 2e5要求输出树上经过每个节点的最长路径。我第一反应是“对每个点跑一次树形 DP 求最长链”写完样例一测复杂度 O(N²)别说 2e51 万节点都跑不动。后来我才意识到这就是换根 DP 的经典模型通过两次 DFS把“以每个节点为根”的答案全部算出来总复杂度 O(N)。这篇文章就把这个模型从头到尾拆开讲——状态怎么设计、转移为什么这样写、代码模板怎么搭以及我在实盘提交时踩过的几个坑。文章适合三类读者一是刚学树形 DP、想知道“每个点都要答案”怎么优化的选手二是刷题时遇到类似“每个节点的 xxx 路径”却只会对每个点重新 DFS 的入门者三是想快速套模板解决换根类题目的竞赛选手。看懂这篇文章后你会发现这类题的核心就一句话把一个点的所有“方向”都求出来答案就是从这些方向里挑两个最长的加起来。1. 从“求直径”到“每个点的答案”问题定义不是一回事1.1 为什么朴素做法注定 O(N²)先厘清一个容易混淆的概念。普通“求树的直径”只需要一个全局最大值跑两次 DFS 或者一次树形 DP 就结束了复杂度 O(N)。但本题要求的是每个节点作为路径交点或者说路径必须经过它时的最长路径长度这是一个长度为 N 的答案数组。最直接的做法就是枚举每个节点 u以 u 为根重新对整棵树做一次 DFS求出“以 u 为根时树内直径”。这个思路本身没问题因为以 u 为根时经过 u 的最长路径确实就是以 u 为根时树的直径但代价是每个点都要遍历整棵树总共 O(N²)。当 N2e5 时这就等于完全不可行。关键是要想明白经过 u 的最长路径本质上只由 u 周围那些“方向”决定不需要真的把整棵树以 u 为根重新建一遍。1.2 一次 DFS 为什么不够假设我们随便选一个根比如节点 1做第一次 DFS能算出什么能算出每个节点在子树内部的最长延伸距离比如从某个节点往下走最远能走到哪。但一个节点的父方向信息也就是它通往父亲那边还能延伸多远在第一次 DFS 里是拿不到的。这里必须举一个例子否则后面公式很难理解。考虑这棵树1 - 2 - 3 - 4 - 5 - 6 | 7主链是 1-2-3-4-5-6节点 7 挂在 3 上。整棵树的直径是 1 到 6长度 5。但经过节点 7 的最长路径是多少是 7-3-4-5-6长度 4也可以是 7-3-2-1长度 3所以答案是 4。直径 1-6 这条路径根本不过 7。这说明一个很反直觉的结论每个节点的答案不一定等于树的直径。要算节点 7 的答案就必须知道它“往上走”能延伸多远也就是父方向的深度。第一次 DFS 只做自底向上根本覆盖不了这种父方向信息所以必须要有第二次“从上往下”的换根过程。1.3 破题思路把“方向”当成基本单位整道题的核心观察可以浓缩成一句话任意一条经过节点 u 的路径从 u 出发可以看作向两个不同的方向各延伸一段距离。比如 u 有子树方向 A、子树方向 B、父方向 C 三个方向那么经过 u 的最长路径就是这三个方向里最长的两个方向深度之和。如果 u 只有一个有效方向比如它是叶子节点那路径的一个端点就是 u 本身此时答案等于那个方向的最大深度。于是问题被拆成了两个小问题对每个节点求出它能向每个邻边方向延伸的最大深度从这些方向深度中取最大的两个相加。第一次 DFS 解决“子树方向”第二次 DFS 解决“父方向”。“换根”的本质就是把父方向的信息从父节点传递给子节点。2. 第一次 DFS自底向上摸清每个节点的“长臂”2.1 状态定义子树方向的最长距离定义f[u]从 u 出发只往子树内部走能走到的最远距离按边数计。叶子节点的f[u] 0。它的转移非常简单f[u] max( f[v] 1 , 0 ) // v 是 u 的孩子这个状态有什么用它相当于知道了“u 通往某个子节点 v 时这条方向最多能延伸多少”。如果 u 有多个孩子每个孩子方向都有一个深度值那么“经过 u 且两端都在子树内的最长路径”就是这些深度值中最大的两个相加。看到“最大的两个”敏感的读者应该已经意识到了只记最大值不够。因为第二次 DFS 要计算父方向贡献时经常需要知道“除某个孩子外其余孩子方向的最大深度”。如果最深方向恰好来自那个孩子就不得不使用次大值。所以第一次 DFS 里我给每个节点维护四个量变量含义best1[u]u 的所有孩子方向深度中的最大值from1[u]这个最大值来自哪个孩子节点best2[u]u 的所有孩子方向深度中的次大值f[u]等于best1[u]单独存只是方便理解2.2 为什么维护次大值就能解决“排除某个子树”在换根阶段我们要计算“u 的除 v 外所有子树方向的最大值”。如果最大值best1[u]恰好来自 v那就只能用次大值best2[u]否则直接使用best1[u]。有了from1[u]做一个判断就能在 O(1) 时间内知道答案不需要把 u 的所有孩子重新遍历一遍。这就是为什么第一次 DFS 不写成“每个点都暴力枚举所有孩子重新求一遍”那样复杂度会退化。一次 DFS 内同时维护最大、次大和来源节点整体复杂度仍然是每个节点只访问常数次总共 O(N)。2.3 第一次 DFS 的代码实现我用 C 写一版邻接表存图递归实现。#include bits/stdc.h using namespace std; const int N 200005; vectorint g[N]; int f[N]; // 从 u 出发只往子树方向走的最远距离 int best1[N]; // 子树方向最大值 int best2[N]; // 子树方向次大值 int from1[N]; // 子树方向最大值来自哪个子节点 int up[N]; // 父方向最大深度第二次 DFS 再填 int ans[N]; // 最终答案 void dfs1(int u, int p) { best1[u] 0; best2[u] 0; from1[u] -1; for (int v : g[u]) { if (v p) continue; dfs1(v, u); int val f[v] 1; // 从 u 走到 v再在 v 的子树里继续向下 if (val best1[u]) { best2[u] best1[u]; best1[u] val; from1[u] v; } else if (val best2[u]) { best2[u] val; } } f[u] best1[u]; }注意这里我从叶子开始自底向上更新所以整棵子树信息先算好父亲才能用孩子的结果。best1和best2的更新逻辑是最经典的“维护最大次大”拿新值依次和最大、次大比较写多了闭着眼都能背。2.4 手算例子第一次 DFS 后的值还是用刚才那棵树令根为 11 - 2 - 3 - 4 - 5 - 6 | 7从叶子往根推6 是叶子best1[6]0, best2[6]05 的孩子是 6val f[6]1 1所以best1[5]1, best2[5]04 的孩子是 5val f[5]1 2所以best1[4]2, best2[4]03 的孩子有 4 和 7从 4 方向得到val f[4]1 3从 7 方向得到val f[7]1 1。所以best1[3]3, from1[3]4, best2[3]12 的孩子只有 3val f[3]1 4所以best1[2]4, best2[2]01 的孩子只有 2val f[2]1 5所以best1[1]5, best2[1]0看到这里就明白了best1[3]3表示从 3 出发往 4 方向走能延伸 3 条边到 6best2[3]1表示往 7 方向能延伸 1 条边。但 3 的父方向往 2、1 方向还没算出来这就是第二次 DFS 的任务。3. 第二次 DFS把父方向“接”下去完成真正的换根3.1 核心状态 up[u]定义up[u]从 u 出发往父节点方向走最多能延伸多少条边。根节点的up[root] 0表示根没有父方向。这里要强调一个容易困惑的点up[u]不只是“走到父节点这一步”而是“从 u 出发先经过父节点 p然后在 p 处选择一个不回到 u 的方向继续往下延伸”的最远距离。如果 p 那边也没别的方向可走了那就在 p 处停下来此时从 u 到 p 这段距离是 1。所以up[u]的最小值其实是 1前提是 u 不是根因为它至少包含一条边 u-p。3.2 换根转移公式从 u 到子节点 v现在假设我们已经在处理节点 u并且已知up[u]的正确值。对 u 的每个孩子 v我们要计算up[v]。从 v 出发往父方向走路径一定是这样的v - u - [在 u 处选择一条不走 v 的最大方向继续延伸]在 u 处能选的“不走 v 的方向”有两类u 的某个孩子方向排除 v最大深度可能是best1[u]或best2[u]取决于best1[u]是否来自 vu 的父方向up[u]。所以公式是up[v] 1 max( up[u] , (v from1[u] ? best2[u] : best1[u]) )这里的1对应边u-v。括号里那一大串取的是“u 在不经过 v 的前提下还能延伸的最大深度”。如果 u 除了 v 以外既没有别的孩子方向up[u]也为 0那么括号里取到 0up[v]1表示 v 向上走到 u 就停住了。3.3 每个节点答案的完整公式有了best1[u]、best2[u]、up[u]u 的所有有效方向就是子树方向最大best1[u]子树方向次大best2[u]父方向up[u]答案等于这三个方向中最大的两个之和。这里有一个新手很容易写错的点我单独拎出来说。有人会想“答案不就是best1[u] max(best2[u], up[u])吗”仔细分析这个式子它其实也是对的因为best1[u] best2[u]所以无论up[u]插在哪里三个候选里最大的两个一定是“最大值 剩余最大值”。但我个人建议代码里直接写成三个值排序取前两个相加逻辑最不容易错尤其后期如果状态多了公式一变就会翻车。3.4 第二次 DFS 的代码实现void dfs2(int u, int p) { // 答案取三个方向中的最大两个相加 int arr[3] {best1[u], best2[u], up[u]}; sort(arr, arr 3, greaterint()); ans[u] arr[0] arr[1]; for (int v : g[u]) { if (v p) continue; // 计算 u 在不经过 v 的前提下还能延伸的最大深度 int cand (from1[u] v ? best2[u] : best1[u]); cand max(cand, up[u]); up[v] cand 1; dfs2(v, u); } }主函数里先调用dfs1(1, 0)然后up[1] 0;再dfs2(1, 0);最后输出ans[i]即可。3.5 手动跑一遍换根过程接着上面的例子我们看几个关键节点的up和答案。根 1 的up[1] 0best1[1]5, best2[1]0所以ans[1] 5 0 5。经过 1 的最长路径就是 1-2-3-4-5-6长度 5正确。处理 1 的孩子 2from1[1] 2为真所以cand best2[1] 0再和up[1]0取最大得 0up[2] 0 1 1。这个结果符合直觉2 往上走只能走到 1 就停了深度 1。处理节点 2 时它的best1[2]4, best2[2]0, up[2]1ans[2] 4 1 5。经过 2 的最长路径是 1-2-3-4-5-6长度 5正确。继续下传到节点 3处理 2 的孩子 3 时from1[2] 3为真所以cand best2[2] 0和up[2]1取最大得 1up[3] 1 1 2。这个值表示从 3 往父方向走最远能延伸到 1距离 23-2-1。节点 3 的best1[3]3, best2[3]1, up[3]2ans[3] 3 2 5。经过 3 的最长路径是 1-2-3-4-5-6长度 5正确。再看节点 7处理 3 的孩子 7 时from1[3] 4不等于 7所以cand best1[3] 3和up[3]2取最大得 3up[7] 3 1 4。节点 7 的best1[7]0, best2[7]0, up[7]4ans[7] 4 0 4。这就是我们最早手动算出来的答案7-3-4-5-6长度 4。这一轮走下来所有节点的答案都正确而且每个节点只被访问常数次整体就是 O(N)。4. 边界情况与实测避坑记录4.1 链状树和星形树极端形态的验证写代码是小事真正容易出问题的是边界情况。我按两种极端树形验证过公式。链状树1-2-3-4-...-n。每个节点最多两个方向比如中间的节点 u它的子方向深度和父方向深度刚好组成两个方向。以 n4 的链为例经过 2 的最长路径是 1-2-3-4长度 3。用代码跑best1[2]2向 3、4 方向best2[2]0up[2]1向 1答案213正确。链状树同时是递归深度最大的情况最容易爆栈下面会讲。星形树中心 1 连接 n-1 个叶子。中心节点 1 的best1[1]1, best2[1]1, up[1]0答案112即经过中心的最长路径是连接两个叶子的路径。叶子节点 2 的best1[2]0, best2[2]0up[2]1max(best1[1]除2外的方向, up[1])2让我们细算一下处理 1 的孩子 2 时from1[1]可能等于 2cand best2[1]1up[2]112。于是叶子 2 的答案022也正确它最远能走到另一个叶子。4.2 n1 的单点树当 N1 时图中没有任何边。dfs1(1,0)后best1[1]0, best2[1]0up[1]0ans[1]0。输出 0没有边数可走正确。但别忘了在输入阶段特判一下因为很多模板代码会先读 n然后循环 n-1 次读边。n1 时循环次数为 0直接算答案输出没有任何问题但如果你习惯用 1-index 的邻接表要注意vector不要越界。4.3 递归栈溢出2e5 的链状树直接教做人这是我最想强调的坑。C 的递归在链状树且 N2e5 时递归深度就是 2e5默认栈大小基本必爆。我第一次提交时本地小数据全过一上大数据的链状树直接 Segmentation Fault查了半天才发现是栈溢出。我的处理方式有两种在代码开头加编译选项例如在 Linux 下ulimit -s unlimited或者在代码里用系统调用sys.setrlimit但这只在部分评测环境有效。更稳妥的做法把递归改成显式栈的迭代写法。不过实际竞赛中如果平台允许调栈我一般直接#pragma comment(linker, /STACK:102400000,102400000)Windows 下 MSVC或者用ulimit能省很多时间。如果你用 Python 写记得sys.setrecursionlimit(1 25)只是提高了递归深度上限真到了 2e5 的链状树Python 递归依然可能触发栈问题建议直接用迭代栈或循环实现两次 DFS。4.4 常见错误整理我把写换根 DP 时最容易踩的坑列成表提交前对着检查一遍错误类型具体表现根源from1判断写反该排除的子树没排除答案偏大没想清楚from1[u]记录的是最佳方向来源忘记把up[u]纳入候选子节点up只考虑了兄弟子树丢了祖父方向父方向是多层累积的不能只算一层答案公式写错写成best1best2丢掉了可能的父方向三个方向必须全量取 top2建图漏边只加单向边断成森林无根树必须双向建边递归爆栈大数据段错误链状树递归深度过大把路径长度按节点数算答案全部偏大 1边数 vs 节点数约定要一致看题目要求这里重点解释一下“忘记把up[u]纳入候选”这个错误。当我们在节点 u 要传给子节点 v 时u 能选的方向除了它的子树还有它自己的父方向。如果只取best1/best2那往上的方向就断了v 的父方向只能延伸到 u 这一层再往上就没了。这会导致整条链中间段子的答案少算。我第一次就是栽在这后来在纸上画了两层以上的树才反应过来。4.5 关于“长度为边数还是节点数”的约定这个问题看似小但真的很坑。有的题目说“路径长度 经过的边数”有的说“路径包含的节点数”。如果按节点数算上面所有状态都应该写成“节点数”也就是叶子节点f[u]1转移val f[v] 1根节点答案ans arr[0] arr[1] - 1因为公共交点 u 被算了两遍。所以写任何树形 DP 之前先确认题目用的是哪种定义否则样例过、最终 WA 得不明不白。5. 从本题延伸出去的几个经典变式5.1 求每个点到所有节点的最远距离这是换根 DP 最常见的变式也是我强烈建议顺手掌握的。题目会问对每个节点求它到树上任意节点的最大距离。答案其实就是ans[u] max(best1[u], up[u])和本题的差别在于本题要求“经过 u 的一条路径”需要两个方向相加而“从 u 出发的最远距离”只需要一个方向。代码只需改动答案计算那一行其他全部相同。我在面试里遇到过好几次这个变体套路完全一致先dfs1维护子树最远再dfs2维护父方向最远最后max合并。5.2 带权边版本如果树的边带权值且权值为正转移公式里的1全部改成w状态含义变为“路径权值和”。比如int val f[v] w; up[v] max(cand, w) ; // 注意 cand 已经是权值和up[v] cand w?严格写是up[v] cand w其中cand是“从 u 不经过 v 延伸的最大权值和”。权值为正时这个转移完全没问题。但如果边权有负数情况会变复杂因为最长路径可能“走到一半就停”不能无条件累加。这时f[u]需要改成max(0, f[v] w)之类的形式表示可以不往下走。这个扩展有点深本文先不展开遇到具体题再单独处理。5.3 树形“先自底向上、再自顶向下”的统一框架换根 DP 的本质是两次 DFS第一遍把子树信息传上去第二遍把父侧信息传下来。这个框架适用于大量“每个点都要全局视角”的树上问题比如求每个节点作为根时整棵树的某种指标重心、子树大小、点数距离和等求每个节点到所有点的距离和经典题“Tree Distances”求每个节点经过它的最长路径求每个节点删除后各连通块的最大大小树的重心判断。一旦你理解了“方向”这个概念遇到这类题第一反应就不再是对每个点重新 DFS而是想这个答案由哪些方向组合而成能不能用两次 DFS 传递5.4 如果要输出具体路径怎么办有些题不仅要求长度还要求输出这条最长路径的两个端点或者路径本身。换根 DP 也能做但需要额外记录每个方向延伸到的端点节点。思路是best1[u]不只记录深度值还要记录这个最深方向通向哪个叶子节点。换根时up[v]对应的端点也要同步传递。这样一个节点的答案取两个方向时就能同时拿到两个端点。但要注意这时次大值best2[u]也必须记录端点。我建议封装一个结构体struct Dir { int len; int endpoint; };这样best1、best2、up都存“长度 端点”维护起来虽然代码变长但逻辑更清晰排查问题也方便。5.5 关于内存与常数的实测体验这个算法需要best1[N]、best2[N]、from1[N]、up[N]、ans[N]五个 int 数组2e5 的数据规模只占几 MB 内存几乎可以忽略。时间复杂度严格 O(N)因为每条边在两次 DFS 中各被访问一次每个节点做常数次比较和赋值。实测下来即使 N1e6 的树在 C 下也能轻松跑完。真正限制性能的通常不是算法本身而是输入输出。记得开ios::sync_with_stdio(false); cin.tie(0);不然大数据输入就能把你卡到怀疑人生。写在最后的一个建议换根 DP 这个模型我在比赛中至少见过七八种包装方式有的问“树上每个点作为起点的最长路径”有的问“删除每条边后两棵子树最大深度之和”有的问“每个点重新作为根时树高是多少”。剥掉外壳全部都是这套两次 DFS 的骨架。个人经验是理解这个模型的关键不在于背代码而在于想明白状态up的传递到底在传什么。我当年卡住时的困惑是“为什么第二遍 DFS 不是真的把根换过去重新算一遍”后来想通了换根不是物理上把树重新拎起来而是把父方向当成一种特殊的方向像接力棒一样从父节点传给子节点。第一遍 DFS 是自底向上汇总第二遍是自顶向下分发。你在刷题时如果也遇到换根 DP建议先用本文最后这个示例树自己手推一遍best1、best2、up、ans四个数组跑通之后再去看代码会顺畅很多。再遇到“每条边删除后的 xxx”或者“每个节点重新作为根时的 xxx”你就能一眼识破这题八成就是换根 DP 变了个马甲。