换根DP详解：两次DFS求树上每个节点的最长路径

换根 DP 这个模型，我最早是在一场模拟赛里被狠狠折磨过一次。题目给出一棵 N 个节点的无根树，N 开到 2e5，要求输出树上经过每个节点的最长路径。我第一反应是“对每个点跑一次树形 DP 求最长链”，写完样例一测，复杂度 O(N²)，别说 2e5，1 万节点都跑不动。

后来我才意识到，这就是换根 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²)。当 N=2e5 时，这就等于完全不可行。

关键是要想明白：经过 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 本身，此时答案等于那个方向的最大深度。

于是问题被拆成了两个小问题：

1. 对每个节点，求出它能向每个邻边方向延伸的最大深度；
2. 从这些方向深度中取最大的两个，相加。

第一次 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 里，我给每个节点维护四个量：

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; vector<int> 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 后的值

还是用刚才那棵树，令根为 1：

1 - 2 - 3 - 4 - 5 - 6 | 7

从叶子往根推：

• 6 是叶子：best1[6]=0, best2[6]=0
• 5 的孩子是 6：val = f[6]+1 = 1，所以best1[5]=1, best2[5]=0
• 4 的孩子是 5：val = f[5]+1 = 2，所以best1[4]=2, best2[4]=0
• 3 的孩子有 4 和 7：从 4 方向得到val = f[4]+1 = 3，从 7 方向得到val = f[7]+1 = 1。所以best1[3]=3, from1[3]=4, best2[3]=1
• 2 的孩子只有 3：val = f[3]+1 = 4，所以best1[2]=4, best2[2]=0
• 1 的孩子只有 2：val = f[2]+1 = 5，所以best1[1]=5, best2[1]=0

看到这里就明白了，best1[3]=3表示从 3 出发往 4 方向走能延伸 3 条边（到 6），best2[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 的方向”，有两类：

1. u 的某个孩子方向（排除 v），最大深度可能是best1[u]或best2[u]，取决于best1[u]是否来自 v；
2. u 的父方向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，那么括号里取到 0，up[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, greater<int>()); 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] = 0，best1[1]=5, best2[1]=0，所以ans[1] = 5 + 0 = 5。经过 1 的最长路径就是 1-2-3-4-5-6，长度 5，正确。

处理 1 的孩子 2：from1[1] == 2为真，所以cand = best2[1] = 0，再和up[1]=0取最大得 0，up[2] = 0 + 1 = 1。这个结果符合直觉：2 往上走只能走到 1 就停了，深度 1。

处理节点 2 时，它的best1[2]=4, best2[2]=0, up[2]=1，ans[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取最大得 1，up[3] = 1 + 1 = 2。这个值表示从 3 往父方向走，最远能延伸到 1，距离 2（3-2-1）。

节点 3 的best1[3]=3, best2[3]=1, up[3]=2，ans[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取最大得 3，up[7] = 3 + 1 = 4。

节点 7 的best1[7]=0, best2[7]=0, up[7]=4，ans[7] = 4 + 0 = 4。这就是我们最早手动算出来的答案：7-3-4-5-6，长度 4。

这一轮走下来，所有节点的答案都正确，而且每个节点只被访问常数次，整体就是 O(N)。

4. 边界情况与实测避坑记录

4.1 链状树和星形树：极端形态的验证

写代码是小事，真正容易出问题的是边界情况。我按两种极端树形验证过公式。

链状树（1-2-3-4-...-n）。每个节点最多两个方向，比如中间的节点 u，它的子方向深度和父方向深度刚好组成两个方向。以 n=4 的链为例，经过 2 的最长路径是 1-2-3-4，长度 3。用代码跑：best1[2]=2（向 3、4 方向），best2[2]=0，up[2]=1（向 1），答案2+1=3，正确。链状树同时是递归深度最大的情况，最容易爆栈，下面会讲。

星形树（中心 1 连接 n-1 个叶子）。中心节点 1 的best1[1]=1, best2[1]=1, up[1]=0，答案1+1=2，即经过中心的最长路径是连接两个叶子的路径。叶子节点 2 的best1[2]=0, best2[2]=0，up[2]=1+max(best1[1]除2外的方向, up[1])=2？让我们细算一下：处理 1 的孩子 2 时，from1[1]可能等于 2，cand = best2[1]=1，up[2]=1+1=2。于是叶子 2 的答案0+2=2，也正确，它最远能走到另一个叶子。

4.2 n=1 的单点树

当 N=1 时，图中没有任何边。dfs1(1,0)后best1[1]=0, best2[1]=0；up[1]=0；ans[1]=0。输出 0，没有边数可走，正确。

但别忘了在输入阶段特判一下，因为很多模板代码会先读 n，然后循环 n-1 次读边。n=1 时循环次数为 0，直接算答案输出，没有任何问题，但如果你习惯用 1-index 的邻接表，要注意vector不要越界。

4.3 递归栈溢出：2e5 的链状树直接教做人

这是我最想强调的坑。C++ 的递归在链状树且 N=2e5 时，递归深度就是 2e5，默认栈大小基本必爆。我第一次提交时本地小数据全过，一上大数据的链状树直接 Segmentation Fault，查了半天才发现是栈溢出。

我的处理方式有两种：

1. 在代码开头加编译选项，例如在 Linux 下：

ulimit -s unlimited

或者在代码里用系统调用sys.setrlimit，但这只在部分评测环境有效。

2. 更稳妥的做法：把递归改成显式栈的迭代写法。不过实际竞赛中，如果平台允许调栈，我一般直接#pragma comment(linker, "/STACK:102400000,102400000")（Windows 下 MSVC）或者用ulimit，能省很多时间。

如果你用 Python 写，记得sys.setrecursionlimit(1 << 25)只是提高了递归深度上限，真到了 2e5 的链状树，Python 递归依然可能触发栈问题，建议直接用迭代栈或循环实现两次 DFS。

4.4 常见错误整理

我把写换根 DP 时最容易踩的坑列成表，提交前对着检查一遍：

这里重点解释一下“忘记把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 中各被访问一次，每个节点做常数次比较和赋值。

实测下来，即使 N=1e6 的树，在 C++ 下也能轻松跑完。真正限制性能的通常不是算法本身，而是输入输出。记得开：

ios::sync_with_stdio(false); cin.tie(0);

不然大数据输入就能把你卡到怀疑人生。

写在最后的一个建议

换根 DP 这个模型，我在比赛中至少见过七八种包装方式：有的问“树上每个点作为起点的最长路径”，有的问“删除每条边后两棵子树最大深度之和”，有的问“每个点重新作为根时树高是多少”。剥掉外壳，全部都是这套两次 DFS 的骨架。

个人经验是，理解这个模型的关键不在于背代码，而在于想明白状态up的传递到底在传什么。我当年卡住时的困惑是：“为什么第二遍 DFS 不是真的把根换过去重新算一遍？”后来想通了：换根不是物理上把树重新拎起来，而是把父方向当成一种特殊的方向，像接力棒一样从父节点传给子节点。第一遍 DFS 是自底向上汇总，第二遍是自顶向下分发。

你在刷题时如果也遇到换根 DP，建议先用本文最后这个示例树自己手推一遍best1、best2、up、ans四个数组，跑通之后再去看代码，会顺畅很多。再遇到“每条边删除后的 xxx”或者“每个节点重新作为根时的 xxx”，你就能一眼识破：这题八成就是换根 DP 变了个马甲。