先说结论这是我近期做过的对“换根法”最友好的一道树形 DP 题——3772. 子图的最大得分我本地题单编号 2235 里把它放在第一位。它把图论、DFS、换根法三个高频考点压进同一道题想 AC 它不能只靠背模板必须把两遍 DFS 到底在传递什么想清楚。题目本身不复杂给你一棵带点权的树点权可正可负。对每个节点 x要你求出“必须包含 x 的连通子图”的最大得分得分就是子图里所有点权之和。注意两个重点第一选出来的点必须连成一片不能东一块西一块第二点权可能是负数所以“强制包含某个点”不一定划算。最后取所有节点里的最大值作为答案也有的题会要求把每个点的结果都输出。为什么这道题值得单独写一篇因为很多刷题人对“换根法”的理解停留在表面见过模板但不知道为什么第一遍 DFS 算的是向下贡献第二遍 DFS 传的是向上贡献。这道题恰好把所有绕的地方都暴露出来了如果只跑一遍 DFS你只能拿到“以某个固定根为视角”的答案但题目要的是“每个点强制作为连通块一员”的答案必须换根。下面的内容我会从暴力思路讲起逐步推导到两遍 DFS每一步该做什么、容易错在哪里都会标明。1. 题意与思路拆解这道题到底在问什么1.1 从“最大连通子图”到“强制包含某个点”先确认一下概念。树上的连通子图就是把若干个节点挑出来并且挑出来的节点之间任意两个都能通过“仍然被挑中的节点”走通。因为输入是树所以一个连通子图本质上就是一棵“局部树”。题目要求的答案是针对每个节点 x 的在所有包含 x 的连通子图中得分最大是多少。我习惯把这个答案记成 ans[x]。最后问你“子图的最大得分”就是 max(ans[x])。这里有个容易忽略的陷阱答案可能为负数。如果整棵树的所有点权都是负数你也必须选一个节点组成非空连通子图那答案就是所有点权中的最大值也就是最“不那么亏”的那个点。不能因为不想亏就把集合选成空集除非题目明确说允许空集。那为什么不能直接把所有正点权和邻居都连起来因为点权可负你带着一个负点走可能把整体收益拉低。决策的本质是每个邻居方向到底“带”还是“不带”如果带带哪些分支又该带多深。这跟“最大子段和”的决策逻辑非常像只不过从一个一维数组换到了树上。1.2 为什么暴力会 TLEO(n^2) 的问题最朴素的想法是这样对每个 x把 x 当成根做一次 DFS递归去“收集”每个孩子方向的正收益。因为有负权节点所以孩子返回的收益如果是负数就丢弃如果是正数就累加。这个过程和在一棵树上跑“最大连通块”完全一致。这个做法的复杂度是多少你枚举 n 个点当根每次都要遍历整个图所以是 O(n^2)。如果 n 只有 100随便写都能过但这类树上题的常见规模是 n ≤ 2×10^5O(n^2) 直接超时连优化空间都很小。暴力的问题在于不同根的时候大部分子树信息被重复计算了一遍又一遍。实际上某个节点“往它某个孩子方向看过去的最大收益”是不会因为整棵树的根换到别处而改变的。变的只是“往父节点方向看过去”那个维度的信息。换根法就是抓住这个不变性先用一遍 DFS 把所有朝下的收益算好再用第二遍 DFS 把朝上的收益递推出来。顺便说一句为什么这里不用 BFS树形 DP 要求先算完子树再回溯更新父节点本质是后序遍历。DFS 天然满足这个顺序。BFS 是层序遍历你在处理当前层时孩子层的 DP 值根本还没算出来没法做状态转移。而且换根时父方向的贡献是从上往下传的这也是 DFS 第二次遍历时天然能实现的顺序。1.3 两条关键思路先算向下再补向上我把整道题的解法拆成两个阶段第一阶段任选一个根比如 1 号节点跑一遍 DFS得到每个节点的 down[u]。down[u] 表示“强制包含 u并且只能往 u 的孩子方向扩张能拿到的最大连通块得分”。这个阶段只处理了每个节点朝下的方向。第二阶段再做一遍 DFS从根往叶子方向走。这一遍里维护每个节点的 up[u]表示“从 u 的父节点方向看过来u 最多还能拿到多少贡献”。有了 down[u] 和 up[u]u 的完整答案就是ans[u] down[u] max(0, up[u])为什么父方向要取 max(0, ...)因为如果父方向整体是负收益u 可以果断选择不往父方向走反正题目只要求连通子图包含 u没人规定 u 必须连到它的父节点去。这两遍 DFS 加在一起就是换根法。核心思想可以用一句话概括全局答案减掉某个分支的贡献就等于剩下的贡献。不需要对每个根重新算一遍。2. 第一遍 DFS先算每个点的“下行得分”2.1 状态定义down[u] 到底表示什么在写代码之前我建议先把状态定义刻在脑子里。down[u] 的定义是以 u 作为这一棵子树的根强制包含 u并且只能往 u 的孩子方向延伸能得到的最大连通块得分。这个定义有一个很关键的点down[u] 允许是负数。比如 u 自身点权是 -5而且两个孩子方向也都是负贡献那 down[u] 就是负数。这个负数不能在上层计算的时候被随便抹掉因为它作为“子问题答案”是真实存在的。只有在 u 的父节点决定“要不要带上 u 这个分支”的时候才会用 max(0, down[u]) 做取舍。对叶子节点来说没有孩子方向可以扩展所以直接 down[leaf] w[leaf]。这是整棵递归树的边界条件。2.2 转移方程为什么要对子贡献取 max(0, ...)状态转移方程是这个down[u] w[u] Σ max(0, down[v])其中 v 是 u 的所有孩子。逐个孩子判断如果 down[v] 是正数说明把 v 这个方向整个纳入连通块能增加得分那就带上如果 down[v] 是负数说明这个方向不管怎么连都亏那就不带。注意这里不需要去考虑“只带 v 的一半分支”这种问题因为 down[v] 已经是在“包含 v”的前提下能做出的最优决策如果最优决策都为负说明这个方向没有任何一个有潜力的组合值得保留。这就是子结构最优性在起作用。生活化一点想你开一家店有人上门谈合作。你评估一个合作方时只需要看他最终能给你贡献多少利润。如果他是负数就别合作如果他是正数不管他内部怎么折腾你只拿最终利润。down[v] 就是合作方内部的最终利润。2.3 参考代码第一次深搜C 的写法不算复杂假设邻接表是 vectorvector g点权数组是 wdown 是 long long 数组void dfs1(int u, int fa) { down[u] w[u]; for (int v : g[u]) { if (v fa) continue; dfs1(v, u); down[u] max(0LL, down[v]); } }主函数里从 1 号节点调用 dfs1(1, 0) 就行。注意递归顺序先递归孩子再累加孩子的返回值这保证每个孩子子树完整算完之后父节点才能做决策。我把这种顺序叫“先听后算”是树形 DP 的标准姿势。2.4 跑一组小样例down 是怎么算出来的为了证明这套转移不是玄学我用手算一个小例子。构造一棵 5 个点的树边1-21-32-42-5点权w[1]-2w[2]3w[3]1w[4]-5w[5]4以 1 为根第一遍 DFS 的结果如下节点 u点权 w[u]down[u] 计算过程down[u]54叶子直接取自身44-5叶子直接取自身-5233 max(0, -5) max(0, 4)731叶子直接取自身11-2-2 max(0, 7) max(0, 1)6仔细看 2 号节点它的孩子 4 号点是 -5被截断成 0孩子 5 号点是 4被累加所以 down[2]7。1 号节点看到 2 号分支收益 7、3 号分支收益 1都保留所以 down[1]6。这里有一个值得留意的地方是 down[4]-5 被完整保存下来了并没有因为它是负数就把数组里这个值改成 0。它只是在上层累加时被“跳过”但它作为 4 号节点自己的子问题答案仍然需要存在。3. 第二遍 DFS换根转移拿到完整答案3.1 换根的核心等式ans[u] 由两个方向组成第一次 DFS 做完之后每个点只知道自己“朝下看”的最大收益。但一提到换根问题就来了当父节点不再是父节点而变成一个“邻居”时u 从父节点那边还能拿多少收益我引入第二个数组 up[u]表示 u 从父方向能得到的最大贡献。这个贡献已经包含了 u 父节点本身以及父节点除 u 之外的其他分支但不包含 u 自己。根节点没有父方向所以 up[root] 0。有了 up[u]u 的完整答案就是ans[u] down[u] max(0, up[u])这个公式的逻辑很直接u 能选的连通块要么往孩子方向扩要么往父方向扩。孩子方向的最优收益已经算好了父方向的最优收益就是 up[u]取不取取决于它是否为正。3.2 父方向贡献怎么传up[child] ans[parent] - max(0, down[child])这是整个换根法最核心、也最容易写错的一行。假设当前处理到节点 u我已经算出了 ans[u]现在要遍历 u 的孩子 v计算 v 的 up[v]。思路是这样的ans[u] 是“包含 u 的最优连通块得分”。这个最优连通块里如果 v 方向被选中了它贡献的数值是 max(0, down[v])如果 v 方向没被选中它贡献的就是 0。不管哪种情况从 ans[u] 中减去 max(0, down[v])剩下的就是“u 所在连通块里除掉 v 分支之后还能剩多少资源”。这个剩余资源就是从 v 的角度向上看时父方向能给它提供的最大外部贡献。所以转移公式是up[v] ans[u] - max(0, down[v])拿到 up[v] 之后立刻可以算ans[v] down[v] max(0, up[v])用全班总分的例子来类比ans[u] 是全班总分down[v] 是某个人的成绩。想知道除他之外所有人的总分不需要重新统计只需要用全班总分减去他的成绩。这里唯一的区别是“成绩”已经在 ans[u] 里被做过一次截断处理所以减法也要用同一个截断后的值。3.3 完整参考代码第二遍 DFSvoid dfs2(int u, int fa) { ans[u] down[u] max(0LL, up[u]); for (int v : g[u]) { if (v fa) continue; up[v] ans[u] - max(0LL, down[v]); dfs2(v, u); } }主流程就是dfs1(1, 0); dfs2(1, 0); long long res -4e18; // 或者用题目给出的极小值 for (int i 1; i n; i) res max(res, ans[i]);这段代码两个细节必须说清楚。第一dfs2 里必须先算完 ans[u]再进入孩子节点的循环因为 up[v] 的公式依赖 ans[u]。第二根节点调用时 up[1] 保持为 0不要再给它额外赋值。3.4 样例全流程up 与 ans 递推全过程继续用前面那棵 5 个点的树把 up 和 ans 完整走一遍节点 udown[u]up[u] 计算过程ans[u]16根节点up06 max(0,0) 627up[2] ans[1] - max(0, down[2]) 6 - 7 -1取 07 max(0,0) 731up[3] ans[1] - max(0, down[3]) 6 - 1 51 max(0,5) 64-5up[4] ans[2] - max(0, down[4]) 7 - 0 7-5 max(0,7) 254up[5] ans[2] - max(0, down[5]) 7 - 4 34 max(0,3) 7最终 max(ans) 7对应的是连通块 {2, 5}得分是 3 4 7。稍微验证一下 ans[3]6对应连通块 {1, 2, 3, 5}得分是 -2 3 1 4 6确实是在强制包含 3 的前提下能凑到的最优解。整个过程和手算预期一致。4. 复杂度、正确性与边界测试4.1 时间与空间为什么能做到 O(n)整个算法只做了两遍 DFS每个节点在每一遍里被访问常数次所以时间复杂度 O(n)。空间上需要存邻接表还有 down、up、ans、w 四个辅助数组都是 O(n) 级别。对比暴力 O(n^2)换根法的理论收益是巨大的。当 n 2×10^5 时暴力需要跑 4×10^10 次操作稳超时限换根法只需要约 4×10^5 次操作差距一目了然。这也是为什么树上“对每个点统计一个包含它的最优值”这类问题几乎全用换根法解决。4.2 正确性简述把“全局减局部”想清楚换根法的正确性其实来自两点。第一任意一个点 u 的连通块只能从两类方向获得收益孩子方向和父方向。down[u] 已经把所有孩子方向的最优收益合并了up[u] 又补充了父方向的最优收益所以 ans[u] 不会漏掉任何一种可能的方案。第二up[v] ans[u] - max(0, down[v]) 这个减法保持了信息的一致性。因为 ans[u] 在构造时用的是截断后的孩子贡献所以减去截断后的 down[v]剩下的恰好是“u 方向以及其他孩子方向”的净收益。这个剩余值作为 v 的父方向贡献信息没有丢失也没有被重复计算。最后还要解释一个容易让人懵的点为什么全局最大答案等于 max(ans[u])假设真正的最优连通块是 B任取 B 里的一个点 u那么 ans[u] 至少不会小于 score(B)因为 B 本身就是一个包含 u 的合法连通子图而 ans[u] 是在所有包含 u 的连通子图里取最大。因此 max(ans) 一定不小于全局最优。反过来每个 ans[u] 都对应某个合法连通子图它的得分不可能超过全局最优。两端一夹max(ans) 就等于全局最优。这就是为什么最后只需要遍历取最大值不用做额外处理。4.3 边界情况测试全正数、全负数、单点、链我建议在提交前先用几个极端小数据验证自己的实现数据特征预期行为最容易犯的错只有 1 个点ans w[1]数组初始化遗漏或递归边界写错所有点权为正答案等于整棵树所有点权之和只算了 down忘加父方向 up所有点权为负答案等于最大的那个点权必须选一个点误把空集当作合法答案返回 0一条链每个点的答案依赖相邻点方向需要换根传递up 传递顺序写反父方向漏算全正数的情况尤其适合拿来检验代码对不对既然所有点都有正收益那每个包含 u 的最优连通块都应该是整棵树所以所有 ans[u] 都等于总和。如果你的代码在某个点上输出比总和小那基本可以断定是 up 的方向没传到位或者负数截断写错了位置。5. 常见问题与避坑实录赛后复盘5.1 常见错误一截断了数组本身而不是截断累加项这个坑我见过太多人踩了。错误写法是在第一遍 DFS 结束后顺手把所有负的 down[u] 改成 0觉得“反正父节点也用不到负数”。这种想法非常危险。down[u] 本身是“包含 u 的最优子问题答案”它可能是负的但这个负值是后面换根减法的重要信息。如果你把它改成 0在计算 up[v] ans[u] - max(0, down[v]) 时减法结果就会偏离真实情况导致答案在更上层被错误放大。正确的做法是数组里永远存原汁原味的 down[u]只在累加和扣减的表达式里写 max(0, down[v])。截断动作只发生在“父节点做决策”的那一刻不能改变子问题本身的答案。5.2 常见错误二递归爆栈和 Python 的递归限制当 n 达到 2×10^5并且树退化成一条链时递归深度就是 2×10^5。C 在部分评测环境下可能直接爆系统栈Python 则基本会在递归到默认上限时报 RecursionError。我的建议是如果你用的是 C可以在本地调试时把栈空间调大一些但说到底想稳妥就自己写手写栈或者用迭代的方式模拟两遍 DFS。如果用的是 Python至少要在读入后加上一句import sys sys.setrecursionlimit(1 25)但即使设置了递归上限Python 在极端链数据下依然有性能风险。对于真正的大规模竞赛题我推荐把递归改成迭代。不过从学习换根法的角度递归版本更容易理解原理我一般建议先把递归版本想明白再考虑优化。5.3 常见错误三换根减法里减错对象再强调一次换根时用的是up[v] ans[u] - max(0, down[v])而不是up[v] ans[u] - down[v]这两个公式只在一个情况下等价那就是 down[v] 恰好是正数。一旦 down[v] 是负数第二个公式会把 up[v] 算大因为你在 ans[u] 里本来就没有计入 v 的负贡献减一个负数反而相当于“多加了一段不存在的资源”。我个人的记忆技巧是ans[u] 里加了什么减法里就减什么。ans[u] 是带着 max 截断累加的所以扣减时也要带 max 截断。5.4 常见问题四和“经典树上最大连通块”模板题分不清没有换根要求的经典题是这样给一棵带权树找一个任意连通块使得分最大。那道题真的只需要一遍 DFSvoid solve(int u, int fa) { long long cur w[u]; for (int v : g[u]) { if (v fa) continue; solve(v, u); cur max(0LL, dp[v]); } dp[u] cur; ans max(ans, cur); }这道题答案直接是全局最大连通块根本不用管“某个点是不是强制被包含”。因为最优连通块不管落在哪里它自己内部一定有一个“局部根”在 DFS 过程中会被当种子记录到 ans 里。而 3772 这道题之所以要换根是因为它要求对每个点单独求解。很多同学分不清两者的区别把第二遍 DFS 省掉样例却也能过因为弱样例根本不会暴露“强制包含某个点”和“全局取最大”之间的差异。记住题目里只要出现“对每个点求包含它的 XX”第一反应就应该是换根法。5.5 同类题目与延伸这道题后面还能怎么变换根法的武器库不止这一种形态。如果把点权换成边权我们依然可以定义每个方向上的“带权贡献”只是转移时要从边权开始累加如果题目要求输出最优方案里选了哪些点那么在第二遍 DFS 时额外记录每个方向是否被选择即可如果从求最大值改成求和、求计数只需要把转移里的 max 改成累加逻辑整体框架完全一致。我本地整理练习清单时特意把编号 2235 这组题设计成了换根法的“全家桶”第一题就是这个最大得分后面几题分别改成求路径长度、求方案数、求每个点作为根时整棵树的最优形态。练完这一组换根法基本就能形成肌肉记忆了。我个人实际练习中的体会是换根法真正的难点永远不是那几行代码而是你脑中能不能把“以 u 为视角的答案”和“以 v 为视角的答案”之间的微差想清楚。建议第一次接触的人不要急着提交代码先拿一个 5 个点的小树把 down、up、ans 三列手算一遍再对照代码理解。做完这一步你会发现之前所有觉得绕的地方其实都归结成一句“全局减局部再加回自己的视野”。最后再分享一个小习惯换根类的题写完我会随机生成 n ≤ 10 的小树和一个 O(n^2) 的暴力程序对拍几轮。两遍 DFS 看起来简单但负数截断、换根顺序、up 初始化这些坑往往要等数据极端一点才会跳出来。对拍能帮你在几分钟内把所有逻辑错误一次暴露干净这个习惯帮我省下的调试时间比任何模板都值钱。