1. 题目还原点对最大值到底要求什么1.1 不只是一道求直径的题最近在某高校程序设计竞赛的赛题里看到一道标号为 A 的题目题名叫点对最大值下方很直接地标出了解法方向换根DP。题面本身不复杂给一棵 n 个节点的无根树每条边带一个正整数权值 w_i定义一个点对 (u, v) 的价值为这两点之间唯一简单路径上的边权之和要求输出所有点对价值的最大值。如果只做到这一步这就是经典的树的直径任选一个起点跑 DFS 找到最远点再从最远点跑一次 DFS 找到另一个最远点直径就出来了。但竞赛题很少会用一个 A 题只考两遍 DFS 求直径因为这类题几乎每个人都练过区分度太低。我看到的版本在原题基础上增加了一个要求对于每个节点 i求出它到树上任意其他节点的最大距离 f[i]最后输出的点对最大值就是所有 f[i] 的最大值。这样一来问题就从找一条最长链变成了求以每个节点为根的最远可达距离换根DP才是这套解法的正题。按照我多年做题的习惯先把数据范围在草稿纸上强调出来n ≤ 100000边权 ≤ 10^9。点对数量是 n(n-1)/2量级在 10^9 以上暴力枚举点对直接排除。边权累加可能到 10^14所以一切距离相关的变量都要用 long long。读题阶段如果忽略了这一点写代码的时候很可能会为了一个 int 溢出调半小时。1.2 为什么点对最大值值得用换根DP刚开始学树形DP的人经常会问求树上最远点对我已经掌握了两次 DFS为什么还要多学一种换根DP要回答这个问题必须把视角从求一条直径切换到每个点都要作为根来算一遍。假设我要算 f[1]也就是节点 1 到所有节点的最远距离只需要从 1 出发 DFS 一遍记录过程中遇到的最大距离。但要算 f[1] 到 f[n] 全部值如果每个起点都跑一次完整 DFS复杂度是 O(n^2)n 到 10^5 的题直接超时。换根DP想解决的就是这件事先对任意选定的根做一次完整 DFS收集所有子树内的信息再做第二次 DFS利用父节点已经算出的答案以 O(1) 的代价把信息从父节点平移给子节点从而把每个节点作为根时的答案都算出来。此外换根DP还有一个更深刻的价值它不依赖直径端点那种特殊性质。两次DFS求直径的成立条件是边权非负且要找的只是全局最远点对。一旦题目改动一下比如每个点带上一个权值路径价值是点权和边权和混合或者边权可以为负数或者要求每个点作为根时统计所有点到它的距离之和两次DFS就未必能直接套用。换根DP不依赖特殊端点它只依赖父子关系把每个节点的答案分成子树方向和父方向两半然后拼起来这种框架天然更通用。1.3 我确定的整体实现框架在写代码前我习惯在纸上画一棵三四个节点的小树把状态转移的依赖关系标出来确定框架无误后再动键盘。这道题的框架可以拆成三块。第一块是后序遍历 DFS。任选 1 号节点作为全局根对每个节点 u计算它子树方向的最远距离 mx[u]同时记录次远距离 se[u] 和最远距离来自哪个子节点from[u]。这里的 se 不是为了炫技它是后面换根时排除某一棵子树的关键。第二块是先序遍历 DFS。维护 up[u]表示从 u 出发第一步走向父节点方向最终能到达的最远距离。根节点 1 没有父节点所以 up[1]0。当遍历到 u 时ans[u] max(mx[u], up[u]) 就得到 u 作为起点的最远距离然后利用 mx[u]、se[u] 和 from[u] 的信息去计算每个子节点 v 的 up[v]。第三块是对所有 ans 取最大值得到点对最大值。这个框架有个形象的比喻把树在节点 u 处切成两半一半是 u 的后院子树另一半是 u 的前院父方向。后院最远距离我已经算好只要把前院最远距离 up[u] 也算出来两者取最大就是整棵树上从 u 出发能走到的最远距离。下面的内容就围绕后院怎么算前院怎么递推展开。2. 第一遍DFS把子树内最远距离和次远距离算清楚2.1 三个关键数组的含义第一次DFS的产物是三个数组mx[u]、se[u]、from[u]。它们的定义必须做到一眼能说出mx[u]在以 u 为根的子树这个范围内从 u 出发沿某条向下的路径走能到达的最远距离。这里的路径完全在子树内不会经过 u 的父节点。se[u]同样在子树范围内从 u 出发能到达的次远距离。注意这个值必须来自和 mx[u] 不同的子节点分支。from[u]mx[u] 对应的那条最远路径第一步走向的子节点编号。如果 mx[u]0表示没有子节点路径可以超过停在原地from[u] 记为 0。很多初学者会把 se 理解成简单的第二大叶子距离之和这是不够的。se 的存在意义是当我在 u 的子节点 v 想要知道除了 v 这棵子树外u 还能往哪里走最远我不能用可能来自 v 的 mx[u]必须用 se[u]。如果 se 与 mx 来自同一个分支排除 v 之后它也不能用。这就是为什么更新时必须保证 se 与 mx 来自不同分支。这个次远距离在链状树上体现不出来但在一个三叉树上就非常明显u 有三棵子树最远和第二远各来自不同的孩子。换根时如果把根从 u 移到第二远那个孩子那么 u 这边能够提供的最远支路是第一远的那棵而不是第三远的。反过来如果把根移到第一远的孩子u 这边只剩第二远可用。所以 se 实际承担的是排除最大分支后的替补最大值这个角色。一个容易忽略的边界是叶子节点。叶子节点既没有子节点也没有通往父方向的边需要考虑。在第一遍DFS结束后叶子的 mx、se 都被初始化为 0表示停在原地不动也是一种合法选择。这对应点对距离里 ij 的情况虽然 ij 不算真正的点对但保留 0 作为基准值不会让答案变小而且方便后续所有节点统一处理。2.2 后序遍历的更新逻辑第一遍DFS采用标准的后序遍历递归处理所有子节点收集完子节点的信息后再用这些信息更新当前节点。核心更新逻辑如下。const int N 100005; struct Edge { int to; long long w; }; vectorEdge g[N]; int n; long long mx[N], se[N], up[N], ans[N]; int from[N]; void dfs1(int u, int fa) { mx[u] se[u] 0; from[u] 0; for (Edge e : g[u]) { int v e.to; long long w e.w; if (v fa) continue; dfs1(v, u); long long cand mx[v] w; if (cand mx[u]) { se[u] mx[u]; mx[u] cand; from[u] v; } else if (cand se[u]) { se[u] cand; } } }这里的 cand mx[v] w表示从 u 走到 v再从 v 出发在 v 的子树内走到最远这条路径的距离。更新逻辑本质上是在维护前三名中的前两名如果新候选比第一名大原来的第一名降级为第二名新候选成为第一名如果新候选只比第二名大就只覆盖第二名。这里有一个值得聊的细节判断条件用的是严格大于还是大于等于。如果两条边的权值相同某个候选恰好等于当前的 mx[u]那么 from[u] 是否更新会影响后面from[u] v的判断。使用严格大于时from[u] 保持最早出现的那条最大分支使用大于等于时from[u] 会被覆盖成较晚遇到的兄弟。两种选择都能得到正确的最终答案因为如果两条分支距离相同无论排除哪一条另一条都能顶上来作为 se[u]se[u] 保存了那个相同的距离。不过为了逻辑清晰我推荐只用严格大于。这样 from[u] 一旦确定就代表最大分支来自 v后面分析分支时不容易绕晕。2.3 实现细节与边界调用 dfs1 时写成 dfs1(1, 0)用 0 作为 1 的假父节点。因为不存在编号为 0 的节点所以递归中不会有人往回走到 0。这在竞赛代码里是很常见的技巧省一个 visited 数组。代码里把所有距离变量声明为 long long。边权可能到 1e9链长可能到 1e5总距离可能到 1e14int 肯定爆。另外mx[u] 初始化为 0 是因为边权都是正数停在原地总比走一条负权路径好。如果题目改成了可能有负权边且要求必须走到另一个不同节点初始化就必须改成 -inf同时叶子节点的处理也要单独设计。这个坑我留在第 5 章专门讲。3. 第二遍DFS换根递推的核心推导3.1 up[u]父方向这条外部路径怎么定义第一遍DFS结束以后我只知道每个节点在自家子树里能走多远。对于非根节点它还有另一片天地父节点方向。从 u 出发走向父节点方向一共有两步先走边 u-fa到达父节点 fa 后再决定是继续往 fa 的父方向走还是往 fa 的其他子树里走。注意这个其他子树必须不包括 u 本身所在的子树否则路径会折返。up[u] 的定义就是从 u 出发第一步走向父节点方向最终能到达的最远距离它包含了从 u 到父节点那条边的权值。根节点 1 没有父方向up[1]0。为什么需要这个定义可以从路径的分类来看。在整棵树里任意一条从 u 出发到别的节点的简单路径第一步要么往某个子节点走要么往父节点方向走。前者意味着路径完全包含在 u 的子树内距离不可能超过 mx[u]后者则必然经过 u 和父节点之间的那条边之后无论走多远都属于 up[u] 的统计范围。这两类是互斥且完备的所以 u 作为根时的最远距离就是这两者的较大者。这个将答案分成子树内外两部分的思路是整个换根DP里最核心的建模方式说白了就是把所有可能走的方向分类分别算出最优再合并。理解了这个后面所有变体题都容易上手。3.2 分支判断来自最大贡献的子节点要排除现在来到整道题最核心的几行代码。假设我已经在第二遍DFS中访问到了节点 u此时 mx[u]、se[u]、from[u]、up[u] 都是已知的。对 u 的每个子节点 v我要根据以下两个候选的较大者来计算 up[v]。第一个候选是继续沿 u 的父方向走。从 v 出发到 u 后沿 u 的父方向最远能走 up[u]这个值已经算好直接用。第二个候选是到了 u 之后不往父方向走而是拐进 u 的子树里某一条路。但绝不能走回 v 的方向所以要从 u 的子树分支里排除 v。此时需要用到 from[u] 和 se[u]如果 from[u] ! v说明 u 的最大分支不在 v 这边那么可以放心地走 mx[u] 这个分支如果 from[u] v说明 u 的最远路径第一步就是走向 v 的这条路不能选只能退而求其次走 se[u] 那个次远分支。然后再加上 u 到 v 的边权得到 up[v]void dfs2(int u, int fa) { ans[u] max(mx[u], up[u]); for (Edge e : g[u]) { int v e.to; long long w e.w; if (v fa) continue; long long out up[u]; if (from[u] v) out max(out, se[u]); else out max(out, mx[u]); up[v] out w; dfs2(v, u); } }这段逻辑需要反复理解的地方是不能走 u 的最大分支的原因。假设 from[u]v也就是 u 的子树里最远的路是先走到 v。如果我在算 up[v] 时也选择这条路径那么 up[v] 的完整路径就是 v - u - v - ...也就是从 v 出发先到 u再立刻回到 v 的子树里。这显然不是简单路径树上点对路径不允许重复经过节点和边。所以在 u 的角度v 这棵子树必须被视为禁区只能从剩下的分支里挑最优的。se[u] 恰恰就是排除最大分支之后的最优选择。3.3 完整代码与主函数有了以上推导主函数部分就很直白了。注意 ans[u] 必须在进入子节点之前计算因为 up[u] 已经是完整的外部最远距离不依赖任何子节点的 up。然后我把 u 的外部信息传递给每一个子节点 vv 拿到 up[v] 后在下一层递归里再计算自己的 ans[v]。int main() { scanf(%d, n); for (int i 1; i n; i) { int u, v; long long w; scanf(%d%d%lld, u, v, w); g[u].push_back({v, w}); g[v].push_back({u, w}); } dfs1(1, 0); up[1] 0; dfs2(1, 0); long long res 0; for (int i 1; i n; i) { res max(res, ans[i]); } printf(%lld\n, res); }如果题目要求输出每个节点的 f[i]在循环里顺便输出 ans[i] 即可。但点对最大值只关心全局最大所以最后取一遍 max。这里我要提醒一点dfs1 和 dfs2 两遍 DFS 的边遍历方式完全一样但作用完全不同。dfs1 是后序先处理子节点再更新父节点dfs2 是先序先算父节点答案再把信息传给子节点。千万不要把两个顺序搞混否则一个节点的 up 会在它的兄弟还没被处理时就传到更深的子节点导致答案错误。4. 正确性验证与复杂度为什么不重不漏4.1 手推一棵小树光看代码还不够我拿一棵简单的树手推一遍大家就能理解所有状态的值是怎么变出来的。假设树是 4 个节点组成的链1-2 边权 12-3 边权 23-4 边权 3。实际数字故意选得不一样方便跟踪。从 1 号开始的 dfs1 递归到底叶子节点 4mx[4]se[4]0from[4]0。节点 3子节点 4 的候选是 033所以 mx[3]3se[3]0from[3]4。节点 2先递归处理子节点 3候选是 325所以 mx[2]5se[2]0from[2]3再处理另一个方向2 的邻点还有 1但是 1 是父节点在 dfs1 中跳过。节点 1子节点 2 的候选是 516mx[1]6se[1]0from[1]2。接下来 dfs2up[1]0ans[1]max(6,0)6。节点 1 的最远点到节点 4距离 6正确。从 1 转移到 2outmax(up[1]0, 因为 from[1]2 所以用 se[1]0) 0up[2]011。dfs2(2) 内部 ans[2]max(5,1)5表示从 2 出发最远到 4距离 5正确。从 2 转移到 3此时 up[2]1from[2]3所以 outmax(1, se[2]0)1up[3]123。ans[3]max(mx[3]3, up[3]3)3表示从 3 出发最远到 1 或 4距离都为 3正确。从 3 转移到 4up[3]3from[3]4outmax(3, se[3]0)3up[4]336。ans[4]6从 4 到 1 距离 6正确。最终 res6也就是 1 到 4 的路径长度是这棵链状树的点对最大值。通过这个推演可以看到up 数组在传递过程中不断累积父方向的信息每一层都依赖上一层已经算好的外部信息。4.2 复杂度与数据范围从代码结构上看dfs1 和 dfs2 各自访问了每条边恰好两次正向一次、反向一次每个节点的常数工作量都是 O(1)所以时间复杂度是 O(n)。空间方面邻接表存边 O(n)mx、se、from、up、ans 都是 O(n)常数不小但对 10^5 的数据来说毫无压力。如果有人用 Python 写要注意递归深度问题建议用迭代栈或提高递归限制用 C 写通常没问题但链状树递归深度同样是 10^5具体做法我放在第 5 章说。这里顺便给一个复杂度之外的提醒这道题的算法是线性的真正限制性能的往往不是复杂度本身而是常量和输入输出。在实际竞赛环境中n 到 10^5 时用 scanf/printf 与 ios::sync_with_stdio(false) 都行关键是别在 DFS 里做高开销操作比如每次递归都 new vector 或拷贝大结构体。如果你的图用邻接表遍历时尽量用引用或者直接读 vector 元素不要为了图省事复制一整条边。输入量最多也就 2e5 个整数scanf 完全够用但如果数据组数很多建议把所有输出用 printf 一次性拼接避免频繁调用 IO 函数。这也是我常年写树题的一个小习惯IO 和遍历的常数必须压住否则线性算法也可能被卡到接近超时。4.3 换根DP vs 两次DFS求直径既然点对最大值本质就是树的直径很多人会纠结是不是用两次 DFS 更简单我很坦白地说如果题目只要求输出直径长度我也会用两次 DFS因为代码量少、出错概率低、心智负担小。但换根DP的优势在于它能拿到每个节点作为起点时的最远距离这一整套信息。两次DFS求直径的做法是从任意点出发找到最远点 A再从 A 出发找到最远点 BA 和 B 就是直径的两个端点。然后从 A 和 B 各跑一次 DFS就能得到每个节点到两个端点的距离每个节点的最远距离等于这两个距离的较大者。这条路在边权非负时完全正确而且代码更短。那为什么还要练换根DP因为很多每个点都要作为根的问题比如第 6 章要讲的树上距离之和、以每个点为根统计子树大小根本没有直径端点这种捷径可走。换根DP提供的是一个统一思维模板第一遍 DFS 汇总子树信息第二遍 DFS 利用父节点答案转移。这个模板覆盖的问题面比两次DFS求直径广得多。所以我的建议是两种都要会但遇到每个点作为根的题优先想换根DP。5. 竞赛里的坑与调试技巧5.1 最大来源记录的是子节点编号不是边这是我第一次写换根DP时踩过的坑。from[u] 应该记录的是最大分支指向的子节点 v而不是u 到 v 这条边的编号。因为我在 dfs2 里判断的是 from[u] v也就是比较节点编号。如果你在存边时用了一个边序号 idwhile 循环里拿到的是当前访问到的边序号和 from[u] 的节点编号对不上就会出 bug。解决办法就是最朴素的from[u] 存节点编号。另外当 mx[u]0 时 from[u] 必须设置为 0表示没有最大来源。如果在初始化时忘了设置默认可能是 0 也可以但如果编译器没清内存值未定义就会导致错误的 from 判断。每次 dfs1 进入节点第一行就赋 from[u]0养成习惯。5.2 0 与 -inf 的选择这道题边权是正数mx[u] 初始化成 0 完全合理。但假设题目改成边权可能为负数且要求 u 必须走到另一个不同节点那么 mx[u] 初始化成 0 就会出错因为一条负权路径可能比停在原地更差但停在原地不构成点对。此时应该把 mx[u] 初始化成 -inf叶子节点也要特殊处理因为它没有子节点路径可选只能依赖 up 方向。更准确地说在负权场景下每个节点的最远距离可能是个负值初始化时要用 -4e18 这种极小值再用候选值来更新。我在实际做题中习惯定义 const long long NEG_INF -(1LL 60)避免手写 -1e9 不够小。还有另一种常见变体边权为点权。每个节点带上权值 a[u]路径价值定义为路径上所有节点权值之和。这时候子节点候选就是 a[v] mx[v]而叶子节点的 mx[u]a[u]不再是 0。初始化逻辑完全不一样。所以每次做题先搞清楚题目求的是边权和还是点权和再决定初始化和递推式。5.3 递归栈溢出与迭代实现n 达到 1e5 时如果树的形态是一条链递归深度就是 1e5。C 在大部分竞赛环境里栈深 1e5 能过但某些系统默认栈空间只有 8MB递归函数里如果还带 vector 遍历和 long long 局部变量可能栈溢出。稳妥的做法是改用显式栈的迭代DFS或者使用系统提供的栈扩展指令。我一般先写递归版本因为清晰然后在小规模数据上测试若担心环境问题再改成迭代。迭代实现换根DP有一点麻烦后序遍历需要先处理完所有子节点再更新父节点所以要用两个栈或者记录每个节点的 child 指针位置。我不建议在赛场上临场改迭代容易写错。更实际的做法是在代码开头加上栈扩展设置或者使用一个自定义的递归深度栈把递归函数改成带状态的循环。如果你的常用环境默认栈足够大递归版最省事。如果你用的是 Python深度限制默认不到 2000直接跑 1e5 深度必炸。需要设置更大的递归上限或者用栈模拟。Python 的递归又慢又吃内存我对这类树的题一般会优先考虑 C。5.4 多组数据的清空问题竞赛题常常有多组测试数据换根DP的数组必须每组数据全部清空。这里有个细节mx、se、from、up、ans 不仅要清空邻接表 vector 也要清空。我习惯在主循环里先把 n 个 vector 全部 clear而不是只 clear n-1 条边涉及的节点因为上一组数据的残留边可能导致越界访问。用一个 while 外层处理多组数据时别忘记 n 也要重新读入。如果上一组 n 是 10 万这一组 n 是 3而 vector 没清DFS 会跑到上一组的节点编号里结果完全不可控。这个错误非常隐蔽因为小数据时可能恰好没有触发越界。5.5 用暴力对拍验证换根DP这类题特别适合对拍验证。随机生成 n≤8 的小树用暴力枚举所有点对求最短路径或者直接跑 Floyd/DFS 求路径和再和换根DP程序的结果对比。对拍跑几百组随机数据如果都没问题正确性基本可以放心。我写对拍的时候会生成无向连通树边权随机选 1 到 100。暴力程序枚举每个起点DFS 一遍得到最远距离把所有起点合并得到全局最大值。这种对拍代码很短却能把from 判断错误se 更新错误初始化问题这类 bug 全部暴露出来。尤其是第 2.2 节提到的严格大于和大于等于的边界对拍多了你就会发现两种写法都行但如果写错了小数据立刻对不上。6. 换根DP的延展从点对最大值到一类树上问题6.1 树中所有点到根的距离之和先看一道非常经典的换根DP变体给一棵 n 个节点的树每条边权为 1对每个节点 u求所有节点到 u 的距离之和 sum[u]。如果对每个 u 都从它出发 DFS 一次复杂度 O(n^2)。用换根DP第一遍 DFS 算两个信息子树大小 siz[u]以及子树内所有点到 u 的距离之和 dp[u]。递推式是 dp[u] sum(dp[v] siz[v])这里边权为 1所以子节点 v 的子树里每个点经过 v 到 u 的距离额外加 1。第二遍 DFS 换根时根从 u 变成 v所有 v 子树内的节点离根的距离减少了 1而 u 另一侧的所有节点离根的距离增加了 1。因此sum[v] sum[u] (n - siz[v]) - siz[v] sum[u] n - 2*siz[v]这就是树上距离和换根公式。可以看到它和点对最大值的换根逻辑一脉相承第一遍汇总子树信息第二遍利用父节点答案做 O(1) 转移。区别只在于这里不需要维护最远和次远只需要维护子树大小和距离总和。6.2 每个点作为根时的最大子树大小另一类常见题是给一棵树对于每个节点 x如果把 x 当作根那么它的所有相邻子树中最大的那棵的大小是多少。这个值常用于求树的重心等。第一遍 DFS 可以算出每个节点在以 1 为根时的子树大小 siz[u]以及所有子节点中最大子树的大小。换根时如果根从 u 换到 vv 的子树之外的那部分大小是 n-siz[v]它成为 u或者说 v 作为根时的一个新子树与原来的子节点子树大小取最大即可。这种题的转移核心同样是父方向补集 n - 子子树大小。正常情况下不需要维护次大因为每个子节点面对的是同一个补集但如果题目还要输出最大子树来自哪个方向就可能需要记录最大和第二大分支和点对最大值的 from/se 设计如出一辙。这正好说明换根DP里排除某个孩子后的替补值这个思想在多种问题里都会反复出现值得专门练熟。6.3 怎么判断一道题该用换根DP还是点分治换根DP和点分治都能处理以每个点为根的树上统计但适用场景不同。我的判断标准很简单如果问题的状态可以拆成子树方向答案 父方向答案并且两个方向能通过 O(1) 的式子合并优先换根DP如果统计要求涉及所有路径的贡献比如统计长度为 k 的路径条数、所有路径权值和的某种聚合换根DP就不太好处理这时候点分治才是正解。在竞赛题里标签写着换根DP的题十有八九只要你做两遍 DFS。第一遍 DFS 收集子树信息第二遍 DFS 从父节点把外部信息传递下来。难点从来不在 DFS 本身而在于你能否设计出正确的状态定义和转移方程。点对最大值这道题的核心收获是先用 from/se 解决排除最大贡献分支的问题再用 up 解决父方向信息传递的问题。这两个手法吃透了换根DP这一整类题你都能应付。 
长河君 · 2026/10/14 18:02:22 · 阅读 1.2k 换根DP详解：从树的直径到每个节点的最远距离
1. 题目还原点对最大值到底要求什么1.1 不只是一道求直径的题最近在某高校程序设计竞赛的赛题里看到一道标号为 A 的题目题名叫点对最大值下方很直接地标出了解法方向换根DP。题面本身不复杂给一棵 n 个节点的无根树每条边带一个正整数权值 w_i定义一个点对 (u, v) 的价值为这两点之间唯一简单路径上的边权之和要求输出所有点对价值的最大值。如果只做到这一步这就是经典的树的直径任选一个起点跑 DFS 找到最远点再从最远点跑一次 DFS 找到另一个最远点直径就出来了。但竞赛题很少会用一个 A 题只考两遍 DFS 求直径因为这类题几乎每个人都练过区分度太低。我看到的版本在原题基础上增加了一个要求对于每个节点 i求出它到树上任意其他节点的最大距离 f[i]最后输出的点对最大值就是所有 f[i] 的最大值。这样一来问题就从找一条最长链变成了求以每个节点为根的最远可达距离换根DP才是这套解法的正题。按照我多年做题的习惯先把数据范围在草稿纸上强调出来n ≤ 100000边权 ≤ 10^9。点对数量是 n(n-1)/2量级在 10^9 以上暴力枚举点对直接排除。边权累加可能到 10^14所以一切距离相关的变量都要用 long long。读题阶段如果忽略了这一点写代码的时候很可能会为了一个 int 溢出调半小时。1.2 为什么点对最大值值得用换根DP刚开始学树形DP的人经常会问求树上最远点对我已经掌握了两次 DFS为什么还要多学一种换根DP要回答这个问题必须把视角从求一条直径切换到每个点都要作为根来算一遍。假设我要算 f[1]也就是节点 1 到所有节点的最远距离只需要从 1 出发 DFS 一遍记录过程中遇到的最大距离。但要算 f[1] 到 f[n] 全部值如果每个起点都跑一次完整 DFS复杂度是 O(n^2)n 到 10^5 的题直接超时。换根DP想解决的就是这件事先对任意选定的根做一次完整 DFS收集所有子树内的信息再做第二次 DFS利用父节点已经算出的答案以 O(1) 的代价把信息从父节点平移给子节点从而把每个节点作为根时的答案都算出来。此外换根DP还有一个更深刻的价值它不依赖直径端点那种特殊性质。两次DFS求直径的成立条件是边权非负且要找的只是全局最远点对。一旦题目改动一下比如每个点带上一个权值路径价值是点权和边权和混合或者边权可以为负数或者要求每个点作为根时统计所有点到它的距离之和两次DFS就未必能直接套用。换根DP不依赖特殊端点它只依赖父子关系把每个节点的答案分成子树方向和父方向两半然后拼起来这种框架天然更通用。1.3 我确定的整体实现框架在写代码前我习惯在纸上画一棵三四个节点的小树把状态转移的依赖关系标出来确定框架无误后再动键盘。这道题的框架可以拆成三块。第一块是后序遍历 DFS。任选 1 号节点作为全局根对每个节点 u计算它子树方向的最远距离 mx[u]同时记录次远距离 se[u] 和最远距离来自哪个子节点from[u]。这里的 se 不是为了炫技它是后面换根时排除某一棵子树的关键。第二块是先序遍历 DFS。维护 up[u]表示从 u 出发第一步走向父节点方向最终能到达的最远距离。根节点 1 没有父节点所以 up[1]0。当遍历到 u 时ans[u] max(mx[u], up[u]) 就得到 u 作为起点的最远距离然后利用 mx[u]、se[u] 和 from[u] 的信息去计算每个子节点 v 的 up[v]。第三块是对所有 ans 取最大值得到点对最大值。这个框架有个形象的比喻把树在节点 u 处切成两半一半是 u 的后院子树另一半是 u 的前院父方向。后院最远距离我已经算好只要把前院最远距离 up[u] 也算出来两者取最大就是整棵树上从 u 出发能走到的最远距离。下面的内容就围绕后院怎么算前院怎么递推展开。2. 第一遍DFS把子树内最远距离和次远距离算清楚2.1 三个关键数组的含义第一次DFS的产物是三个数组mx[u]、se[u]、from[u]。它们的定义必须做到一眼能说出mx[u]在以 u 为根的子树这个范围内从 u 出发沿某条向下的路径走能到达的最远距离。这里的路径完全在子树内不会经过 u 的父节点。se[u]同样在子树范围内从 u 出发能到达的次远距离。注意这个值必须来自和 mx[u] 不同的子节点分支。from[u]mx[u] 对应的那条最远路径第一步走向的子节点编号。如果 mx[u]0表示没有子节点路径可以超过停在原地from[u] 记为 0。很多初学者会把 se 理解成简单的第二大叶子距离之和这是不够的。se 的存在意义是当我在 u 的子节点 v 想要知道除了 v 这棵子树外u 还能往哪里走最远我不能用可能来自 v 的 mx[u]必须用 se[u]。如果 se 与 mx 来自同一个分支排除 v 之后它也不能用。这就是为什么更新时必须保证 se 与 mx 来自不同分支。这个次远距离在链状树上体现不出来但在一个三叉树上就非常明显u 有三棵子树最远和第二远各来自不同的孩子。换根时如果把根从 u 移到第二远那个孩子那么 u 这边能够提供的最远支路是第一远的那棵而不是第三远的。反过来如果把根移到第一远的孩子u 这边只剩第二远可用。所以 se 实际承担的是排除最大分支后的替补最大值这个角色。一个容易忽略的边界是叶子节点。叶子节点既没有子节点也没有通往父方向的边需要考虑。在第一遍DFS结束后叶子的 mx、se 都被初始化为 0表示停在原地不动也是一种合法选择。这对应点对距离里 ij 的情况虽然 ij 不算真正的点对但保留 0 作为基准值不会让答案变小而且方便后续所有节点统一处理。2.2 后序遍历的更新逻辑第一遍DFS采用标准的后序遍历递归处理所有子节点收集完子节点的信息后再用这些信息更新当前节点。核心更新逻辑如下。const int N 100005; struct Edge { int to; long long w; }; vectorEdge g[N]; int n; long long mx[N], se[N], up[N], ans[N]; int from[N]; void dfs1(int u, int fa) { mx[u] se[u] 0; from[u] 0; for (Edge e : g[u]) { int v e.to; long long w e.w; if (v fa) continue; dfs1(v, u); long long cand mx[v] w; if (cand mx[u]) { se[u] mx[u]; mx[u] cand; from[u] v; } else if (cand se[u]) { se[u] cand; } } }这里的 cand mx[v] w表示从 u 走到 v再从 v 出发在 v 的子树内走到最远这条路径的距离。更新逻辑本质上是在维护前三名中的前两名如果新候选比第一名大原来的第一名降级为第二名新候选成为第一名如果新候选只比第二名大就只覆盖第二名。这里有一个值得聊的细节判断条件用的是严格大于还是大于等于。如果两条边的权值相同某个候选恰好等于当前的 mx[u]那么 from[u] 是否更新会影响后面from[u] v的判断。使用严格大于时from[u] 保持最早出现的那条最大分支使用大于等于时from[u] 会被覆盖成较晚遇到的兄弟。两种选择都能得到正确的最终答案因为如果两条分支距离相同无论排除哪一条另一条都能顶上来作为 se[u]se[u] 保存了那个相同的距离。不过为了逻辑清晰我推荐只用严格大于。这样 from[u] 一旦确定就代表最大分支来自 v后面分析分支时不容易绕晕。2.3 实现细节与边界调用 dfs1 时写成 dfs1(1, 0)用 0 作为 1 的假父节点。因为不存在编号为 0 的节点所以递归中不会有人往回走到 0。这在竞赛代码里是很常见的技巧省一个 visited 数组。代码里把所有距离变量声明为 long long。边权可能到 1e9链长可能到 1e5总距离可能到 1e14int 肯定爆。另外mx[u] 初始化为 0 是因为边权都是正数停在原地总比走一条负权路径好。如果题目改成了可能有负权边且要求必须走到另一个不同节点初始化就必须改成 -inf同时叶子节点的处理也要单独设计。这个坑我留在第 5 章专门讲。3. 第二遍DFS换根递推的核心推导3.1 up[u]父方向这条外部路径怎么定义第一遍DFS结束以后我只知道每个节点在自家子树里能走多远。对于非根节点它还有另一片天地父节点方向。从 u 出发走向父节点方向一共有两步先走边 u-fa到达父节点 fa 后再决定是继续往 fa 的父方向走还是往 fa 的其他子树里走。注意这个其他子树必须不包括 u 本身所在的子树否则路径会折返。up[u] 的定义就是从 u 出发第一步走向父节点方向最终能到达的最远距离它包含了从 u 到父节点那条边的权值。根节点 1 没有父方向up[1]0。为什么需要这个定义可以从路径的分类来看。在整棵树里任意一条从 u 出发到别的节点的简单路径第一步要么往某个子节点走要么往父节点方向走。前者意味着路径完全包含在 u 的子树内距离不可能超过 mx[u]后者则必然经过 u 和父节点之间的那条边之后无论走多远都属于 up[u] 的统计范围。这两类是互斥且完备的所以 u 作为根时的最远距离就是这两者的较大者。这个将答案分成子树内外两部分的思路是整个换根DP里最核心的建模方式说白了就是把所有可能走的方向分类分别算出最优再合并。理解了这个后面所有变体题都容易上手。3.2 分支判断来自最大贡献的子节点要排除现在来到整道题最核心的几行代码。假设我已经在第二遍DFS中访问到了节点 u此时 mx[u]、se[u]、from[u]、up[u] 都是已知的。对 u 的每个子节点 v我要根据以下两个候选的较大者来计算 up[v]。第一个候选是继续沿 u 的父方向走。从 v 出发到 u 后沿 u 的父方向最远能走 up[u]这个值已经算好直接用。第二个候选是到了 u 之后不往父方向走而是拐进 u 的子树里某一条路。但绝不能走回 v 的方向所以要从 u 的子树分支里排除 v。此时需要用到 from[u] 和 se[u]如果 from[u] ! v说明 u 的最大分支不在 v 这边那么可以放心地走 mx[u] 这个分支如果 from[u] v说明 u 的最远路径第一步就是走向 v 的这条路不能选只能退而求其次走 se[u] 那个次远分支。然后再加上 u 到 v 的边权得到 up[v]void dfs2(int u, int fa) { ans[u] max(mx[u], up[u]); for (Edge e : g[u]) { int v e.to; long long w e.w; if (v fa) continue; long long out up[u]; if (from[u] v) out max(out, se[u]); else out max(out, mx[u]); up[v] out w; dfs2(v, u); } }这段逻辑需要反复理解的地方是不能走 u 的最大分支的原因。假设 from[u]v也就是 u 的子树里最远的路是先走到 v。如果我在算 up[v] 时也选择这条路径那么 up[v] 的完整路径就是 v - u - v - ...也就是从 v 出发先到 u再立刻回到 v 的子树里。这显然不是简单路径树上点对路径不允许重复经过节点和边。所以在 u 的角度v 这棵子树必须被视为禁区只能从剩下的分支里挑最优的。se[u] 恰恰就是排除最大分支之后的最优选择。3.3 完整代码与主函数有了以上推导主函数部分就很直白了。注意 ans[u] 必须在进入子节点之前计算因为 up[u] 已经是完整的外部最远距离不依赖任何子节点的 up。然后我把 u 的外部信息传递给每一个子节点 vv 拿到 up[v] 后在下一层递归里再计算自己的 ans[v]。int main() { scanf(%d, n); for (int i 1; i n; i) { int u, v; long long w; scanf(%d%d%lld, u, v, w); g[u].push_back({v, w}); g[v].push_back({u, w}); } dfs1(1, 0); up[1] 0; dfs2(1, 0); long long res 0; for (int i 1; i n; i) { res max(res, ans[i]); } printf(%lld\n, res); }如果题目要求输出每个节点的 f[i]在循环里顺便输出 ans[i] 即可。但点对最大值只关心全局最大所以最后取一遍 max。这里我要提醒一点dfs1 和 dfs2 两遍 DFS 的边遍历方式完全一样但作用完全不同。dfs1 是后序先处理子节点再更新父节点dfs2 是先序先算父节点答案再把信息传给子节点。千万不要把两个顺序搞混否则一个节点的 up 会在它的兄弟还没被处理时就传到更深的子节点导致答案错误。4. 正确性验证与复杂度为什么不重不漏4.1 手推一棵小树光看代码还不够我拿一棵简单的树手推一遍大家就能理解所有状态的值是怎么变出来的。假设树是 4 个节点组成的链1-2 边权 12-3 边权 23-4 边权 3。实际数字故意选得不一样方便跟踪。从 1 号开始的 dfs1 递归到底叶子节点 4mx[4]se[4]0from[4]0。节点 3子节点 4 的候选是 033所以 mx[3]3se[3]0from[3]4。节点 2先递归处理子节点 3候选是 325所以 mx[2]5se[2]0from[2]3再处理另一个方向2 的邻点还有 1但是 1 是父节点在 dfs1 中跳过。节点 1子节点 2 的候选是 516mx[1]6se[1]0from[1]2。接下来 dfs2up[1]0ans[1]max(6,0)6。节点 1 的最远点到节点 4距离 6正确。从 1 转移到 2outmax(up[1]0, 因为 from[1]2 所以用 se[1]0) 0up[2]011。dfs2(2) 内部 ans[2]max(5,1)5表示从 2 出发最远到 4距离 5正确。从 2 转移到 3此时 up[2]1from[2]3所以 outmax(1, se[2]0)1up[3]123。ans[3]max(mx[3]3, up[3]3)3表示从 3 出发最远到 1 或 4距离都为 3正确。从 3 转移到 4up[3]3from[3]4outmax(3, se[3]0)3up[4]336。ans[4]6从 4 到 1 距离 6正确。最终 res6也就是 1 到 4 的路径长度是这棵链状树的点对最大值。通过这个推演可以看到up 数组在传递过程中不断累积父方向的信息每一层都依赖上一层已经算好的外部信息。4.2 复杂度与数据范围从代码结构上看dfs1 和 dfs2 各自访问了每条边恰好两次正向一次、反向一次每个节点的常数工作量都是 O(1)所以时间复杂度是 O(n)。空间方面邻接表存边 O(n)mx、se、from、up、ans 都是 O(n)常数不小但对 10^5 的数据来说毫无压力。如果有人用 Python 写要注意递归深度问题建议用迭代栈或提高递归限制用 C 写通常没问题但链状树递归深度同样是 10^5具体做法我放在第 5 章说。这里顺便给一个复杂度之外的提醒这道题的算法是线性的真正限制性能的往往不是复杂度本身而是常量和输入输出。在实际竞赛环境中n 到 10^5 时用 scanf/printf 与 ios::sync_with_stdio(false) 都行关键是别在 DFS 里做高开销操作比如每次递归都 new vector 或拷贝大结构体。如果你的图用邻接表遍历时尽量用引用或者直接读 vector 元素不要为了图省事复制一整条边。输入量最多也就 2e5 个整数scanf 完全够用但如果数据组数很多建议把所有输出用 printf 一次性拼接避免频繁调用 IO 函数。这也是我常年写树题的一个小习惯IO 和遍历的常数必须压住否则线性算法也可能被卡到接近超时。4.3 换根DP vs 两次DFS求直径既然点对最大值本质就是树的直径很多人会纠结是不是用两次 DFS 更简单我很坦白地说如果题目只要求输出直径长度我也会用两次 DFS因为代码量少、出错概率低、心智负担小。但换根DP的优势在于它能拿到每个节点作为起点时的最远距离这一整套信息。两次DFS求直径的做法是从任意点出发找到最远点 A再从 A 出发找到最远点 BA 和 B 就是直径的两个端点。然后从 A 和 B 各跑一次 DFS就能得到每个节点到两个端点的距离每个节点的最远距离等于这两个距离的较大者。这条路在边权非负时完全正确而且代码更短。那为什么还要练换根DP因为很多每个点都要作为根的问题比如第 6 章要讲的树上距离之和、以每个点为根统计子树大小根本没有直径端点这种捷径可走。换根DP提供的是一个统一思维模板第一遍 DFS 汇总子树信息第二遍 DFS 利用父节点答案转移。这个模板覆盖的问题面比两次DFS求直径广得多。所以我的建议是两种都要会但遇到每个点作为根的题优先想换根DP。5. 竞赛里的坑与调试技巧5.1 最大来源记录的是子节点编号不是边这是我第一次写换根DP时踩过的坑。from[u] 应该记录的是最大分支指向的子节点 v而不是u 到 v 这条边的编号。因为我在 dfs2 里判断的是 from[u] v也就是比较节点编号。如果你在存边时用了一个边序号 idwhile 循环里拿到的是当前访问到的边序号和 from[u] 的节点编号对不上就会出 bug。解决办法就是最朴素的from[u] 存节点编号。另外当 mx[u]0 时 from[u] 必须设置为 0表示没有最大来源。如果在初始化时忘了设置默认可能是 0 也可以但如果编译器没清内存值未定义就会导致错误的 from 判断。每次 dfs1 进入节点第一行就赋 from[u]0养成习惯。5.2 0 与 -inf 的选择这道题边权是正数mx[u] 初始化成 0 完全合理。但假设题目改成边权可能为负数且要求 u 必须走到另一个不同节点那么 mx[u] 初始化成 0 就会出错因为一条负权路径可能比停在原地更差但停在原地不构成点对。此时应该把 mx[u] 初始化成 -inf叶子节点也要特殊处理因为它没有子节点路径可选只能依赖 up 方向。更准确地说在负权场景下每个节点的最远距离可能是个负值初始化时要用 -4e18 这种极小值再用候选值来更新。我在实际做题中习惯定义 const long long NEG_INF -(1LL 60)避免手写 -1e9 不够小。还有另一种常见变体边权为点权。每个节点带上权值 a[u]路径价值定义为路径上所有节点权值之和。这时候子节点候选就是 a[v] mx[v]而叶子节点的 mx[u]a[u]不再是 0。初始化逻辑完全不一样。所以每次做题先搞清楚题目求的是边权和还是点权和再决定初始化和递推式。5.3 递归栈溢出与迭代实现n 达到 1e5 时如果树的形态是一条链递归深度就是 1e5。C 在大部分竞赛环境里栈深 1e5 能过但某些系统默认栈空间只有 8MB递归函数里如果还带 vector 遍历和 long long 局部变量可能栈溢出。稳妥的做法是改用显式栈的迭代DFS或者使用系统提供的栈扩展指令。我一般先写递归版本因为清晰然后在小规模数据上测试若担心环境问题再改成迭代。迭代实现换根DP有一点麻烦后序遍历需要先处理完所有子节点再更新父节点所以要用两个栈或者记录每个节点的 child 指针位置。我不建议在赛场上临场改迭代容易写错。更实际的做法是在代码开头加上栈扩展设置或者使用一个自定义的递归深度栈把递归函数改成带状态的循环。如果你的常用环境默认栈足够大递归版最省事。如果你用的是 Python深度限制默认不到 2000直接跑 1e5 深度必炸。需要设置更大的递归上限或者用栈模拟。Python 的递归又慢又吃内存我对这类树的题一般会优先考虑 C。5.4 多组数据的清空问题竞赛题常常有多组测试数据换根DP的数组必须每组数据全部清空。这里有个细节mx、se、from、up、ans 不仅要清空邻接表 vector 也要清空。我习惯在主循环里先把 n 个 vector 全部 clear而不是只 clear n-1 条边涉及的节点因为上一组数据的残留边可能导致越界访问。用一个 while 外层处理多组数据时别忘记 n 也要重新读入。如果上一组 n 是 10 万这一组 n 是 3而 vector 没清DFS 会跑到上一组的节点编号里结果完全不可控。这个错误非常隐蔽因为小数据时可能恰好没有触发越界。5.5 用暴力对拍验证换根DP这类题特别适合对拍验证。随机生成 n≤8 的小树用暴力枚举所有点对求最短路径或者直接跑 Floyd/DFS 求路径和再和换根DP程序的结果对比。对拍跑几百组随机数据如果都没问题正确性基本可以放心。我写对拍的时候会生成无向连通树边权随机选 1 到 100。暴力程序枚举每个起点DFS 一遍得到最远距离把所有起点合并得到全局最大值。这种对拍代码很短却能把from 判断错误se 更新错误初始化问题这类 bug 全部暴露出来。尤其是第 2.2 节提到的严格大于和大于等于的边界对拍多了你就会发现两种写法都行但如果写错了小数据立刻对不上。6. 换根DP的延展从点对最大值到一类树上问题6.1 树中所有点到根的距离之和先看一道非常经典的换根DP变体给一棵 n 个节点的树每条边权为 1对每个节点 u求所有节点到 u 的距离之和 sum[u]。如果对每个 u 都从它出发 DFS 一次复杂度 O(n^2)。用换根DP第一遍 DFS 算两个信息子树大小 siz[u]以及子树内所有点到 u 的距离之和 dp[u]。递推式是 dp[u] sum(dp[v] siz[v])这里边权为 1所以子节点 v 的子树里每个点经过 v 到 u 的距离额外加 1。第二遍 DFS 换根时根从 u 变成 v所有 v 子树内的节点离根的距离减少了 1而 u 另一侧的所有节点离根的距离增加了 1。因此sum[v] sum[u] (n - siz[v]) - siz[v] sum[u] n - 2*siz[v]这就是树上距离和换根公式。可以看到它和点对最大值的换根逻辑一脉相承第一遍汇总子树信息第二遍利用父节点答案做 O(1) 转移。区别只在于这里不需要维护最远和次远只需要维护子树大小和距离总和。6.2 每个点作为根时的最大子树大小另一类常见题是给一棵树对于每个节点 x如果把 x 当作根那么它的所有相邻子树中最大的那棵的大小是多少。这个值常用于求树的重心等。第一遍 DFS 可以算出每个节点在以 1 为根时的子树大小 siz[u]以及所有子节点中最大子树的大小。换根时如果根从 u 换到 vv 的子树之外的那部分大小是 n-siz[v]它成为 u或者说 v 作为根时的一个新子树与原来的子节点子树大小取最大即可。这种题的转移核心同样是父方向补集 n - 子子树大小。正常情况下不需要维护次大因为每个子节点面对的是同一个补集但如果题目还要输出最大子树来自哪个方向就可能需要记录最大和第二大分支和点对最大值的 from/se 设计如出一辙。这正好说明换根DP里排除某个孩子后的替补值这个思想在多种问题里都会反复出现值得专门练熟。6.3 怎么判断一道题该用换根DP还是点分治换根DP和点分治都能处理以每个点为根的树上统计但适用场景不同。我的判断标准很简单如果问题的状态可以拆成子树方向答案 父方向答案并且两个方向能通过 O(1) 的式子合并优先换根DP如果统计要求涉及所有路径的贡献比如统计长度为 k 的路径条数、所有路径权值和的某种聚合换根DP就不太好处理这时候点分治才是正解。在竞赛题里标签写着换根DP的题十有八九只要你做两遍 DFS。第一遍 DFS 收集子树信息第二遍 DFS 从父节点把外部信息传递下来。难点从来不在 DFS 本身而在于你能否设计出正确的状态定义和转移方程。点对最大值这道题的核心收获是先用 from/se 解决排除最大贡献分支的问题再用 up 解决父方向信息传递的问题。这两个手法吃透了换根DP这一整类题你都能应付。