这道题乍一看像是“又一道树形DP”但等你看清数据范围和询问方式才会发现真正的考点是换根法。题目来自图论里非常典型的场景给一棵带点权的树需要以每个节点作为“根”或“连接点”计算某个子图的最大得分。如果对每个点都单独跑一次DFS复杂度直接到O(n^2)n稍微大一点就超时换根法的价值就在于把这一整类“每个点都要当一次根”的问题压缩成两趟DFS解决。这篇内容适合已经会基础树形DP、但看到“换根”就头疼的选手也适合想在赛前突击图论套路的人。我会把状态设计、两趟DFS的职责分工、完整代码和现场踩坑记录全部分享出来尽量让你看完就能直接抄作业。1. 先看懂题目在问什么一次DFS为什么不够1.1 问题抽象与题目场景先把题面翻译成最朴素的模型给定一棵n个节点的树每个节点有一个整数权值w[i]。现在要求你选择一个连通子图子图的得分为子图内所有节点权值之和。但这里有个关键约束——这个连通子图必须以某个指定的节点作为“根”来构建也就是说子图必须包含这个指定节点并且沿树边连通。形如“3772. 子图的最大得分”这类题目通常会把问题包装成对每一个节点u都想求一个以u为“基准点”的最大连通子图得分然后从所有节点中取最大值。更直白一点你可以理解为每次把u固定下来在整棵树里找出一个包含u、且得分最大的连通块。如果对每个u都从零开始做一次DFS那思路非常直观以u为根u自己必须选子树里凡是能带来正收益的分支就选进来负收益的分支全部砍掉。这个贪心是正确的因为连通子图的可选分支彼此独立贡献为正就纳入贡献为负就可以不连。但问题也随之而来n个节点每个都做一遍每次都是O(n)总复杂度O(n^2)。数据量一旦到10^5就是10^10次操作比赛环境里几乎不可能通过。1.2 暴力方案的时间成本我们先具体感受一下暴力为什么不行。假设n10^5树退化成一条链每次以点i为根计算最大得分都要沿着链走完所有其他节点单次是O(n)。10^5个节点全部计算一轮总操作次数大约10^10次。即使每条边访问只是几次简单加法在主流评测机上也要几十秒起步。更难受的是这些计算里有大量重复。以节点1为根时你已经算出节点2到节点10这条链上的所有“向下贡献”以节点2为根时其实只是把根从1换到2其余节点之间的关系没有任何变化但暴力做法会把整棵树重新扫一遍。换根法要解决的就是这种“换根引起的局部变化”把重复利用的结果缓存下来。这也解释了为什么这类题目的数据范围往往卡在10^5级别它就是要逼你用O(n)做法而不是给你留一个暴力过小数据的口子。如果你在赛场上看到“树 每个点都要算一次答案 点权”这三个关键词同时出现第一反应就应该是换根DP而不是急着写一个看起来对但注定超时的DFS。1.3 换根法的切入点换根法的核心思想并不复杂我先随便挑一个节点通常是1号节点作为整棵树的根做一次完整的DFS算出以它为根时的答案然后再从根出发做第二次DFS利用父节点已经算好的信息推导出子节点作为根时的答案。这个过程中最关键的一点是当根从父节点u换到子节点v时整棵树的形态变化非常有限。原本v只是u的一个子树换根之后v成了新的根原来的父节点u所在的整棵“上方区域”变成了v的一个新分支。除此之外v自己的其他子树完全没变。所以我们只需要处理好“u那一侧能对v提供多少贡献”这一个量就能在O(1)时间内从ans[u]推出ans[v]。整个过程一共两次DFS第一次处理“向下看”的信息第二次补全“向上看”的信息最终每个节点的答案由这两部分共同组成。下面把状态定义和转移方程一步步拆开。2. 换根DP的状态设计与转移方程2.1 状态定义两趟DFS各管什么我给每个节点u定义三个关键值这三个值记清楚整个代码就不会乱down[u]从u出发只向u的子树方向扩展所能得到的最大连通块得分。这个连通块必须包含u并且不能越过u的父节点方向。up[u]从u的父节点方向过来所能得到的最大贡献值。也就是说当u作为根时父节点那一侧能额外提供给u的“外部块”得分。ans[u]以u为根时的最终答案公式为ans[u] down[u] max(0, up[u])。为什么要给up加一个max(0, ...)的操作因为外部块可能整体是负收益。既然题目允许子图不包含某些分支那当父节点方向的净贡献为负时最优策略就是干脆不连上去此时外部贡献按0处理。第一趟DFS负责把所有down值算出来这只需要一次自底向上的递归。第二趟DFS负责在自顶向下遍历的过程中逐个计算每个子节点的up值并同步算出ans值。两趟DFS的职责分配可以用下面这张表概括DFS阶段遍历方向计算内容依赖信息第一趟DFS自底向上down[u]所有子节点的down值第二趟DFS自顶向下up[u]和ans[u]父节点的ans值和当前子节点的down值从这张表能看得更清楚down值只依赖子树内部信息所以自底向上up值依赖父节点信息所以必须自顶向下。两者方向相反但又互相补全最终合在一起构成完整答案。2.2 第一趟DFS的转移细节第一趟DFS的转移非常像经典的“子树最大贡献”问题。对于节点u先把u自身的权值计入然后逐个查看它的子节点v如果down[v] 0说明把v这棵子树接入u可以获得正收益那就接进来如果down[v] 0说明v这整棵子树带上之后反而会拉低得分那就完全忽略它。写成方程式就是down[u] w[u] Σ max(0, down[v])这里有一个容易忽略的细节down[v]本身已经包含了节点v的权值和它往下扩展的正收益分支。如果down[v]是正数把v的整个“向下最优连通块”接过来本身就是局部最优的不需要再考虑从v里拆出一部分。这背后的逻辑是连通块的可加性多个子节点分支之间没有交集贡献独立所以每个分支做max(0, ...)后直接累加就是最优。注意u自身必须被选中所以w[u]无条件加入。哪怕w[u]是负数它也得在down[u]里因为down[u]表示“包含u向下的最大得分”u自己是这个连通块的起点不能把自己丢掉。对于根节点1第一趟DFS结束后它的答案直接就是down[1]因为根节点没有父方向。但其他节点的最终答案现在还差一块也就是从父节点方向过来的up值这需要第二趟DFS来处理。2.3 第二趟DFS如何复用结果第二趟DFS从根节点1开始根节点的up[1]初始化为0ans[1] down[1] max(0, up[1]) down[1]。接下来当DFS从当前节点u走向子节点v时要做这样一件事计算“u那一侧剥离掉v这棵子树之后还能给v提供多少贡献”。先想清楚这个值的含义。ans[u]是以u为根时的全局最优连通块得分。当我们要换根到v时原本属于u的子节点v变成了新根v的一个子节点而u以及u的其他分支、再加上u的父方向外部贡献则整体变成了v的一个“外部块”。这个外部块的得分等于ans[u]减去v分支原本在ans[u]中贡献的部分。v分支在ans[u]中的贡献是max(0, down[v])。所以外部块得分就是outside ans[u] - max(0, down[v])如果这个outside是正数v就可以选择接上这块得到额外收益如果它是负数就按0处理。因此up[v] max(0, ans[u] - max(0, down[v]))然后立刻得到ans[v] down[v] up[v]这里有一点特别容易混淆我本身也踩过好几次坑计算up[v]时使用的是ans[u]而不是down[u]。因为v换根之后它面对的父方向不仅包括u自身还包括u的父方向贡献和u的其他正收益子分支。只有用ans[u]这个“完整视角”才能覆盖所有可能给v带来的收益。如果错误地用了down[u]就会丢掉u上方那部分贡献导致最终答案偏小。第二趟DFS还有一个顺序要求必须先算出up[v]再递归进入v。因为v后续计算它的子节点时需要依赖ans[v]而ans[v]又依赖up[v]。如果先递归再计算v的子节点拿到的就是未更新的错误up值结果会全乱。3. 完整代码实现从伪码到可提交版本3.1 邻接表与输入处理树的存储方式直接决定代码风格。我习惯用vector g[n 1]存邻接表因为换根DP需要频繁遍历邻居邻接矩阵会浪费大量空间而且n到10^5量级时根本开不下。输入通常是n和n-1条边节点编号从1到n。这里的建树过程没有太多讲究唯一要注意的是重边和自环问题。虽然题目声明是树时通常不会有重边但部分OJ的输入并不规范如果直接判断v ! parent遇到重边时会把父节点当成另一个子节点再次访问形成死循环。稳妥的做法是判断v ! pre其中pre记录的是“上一层递归进来的节点”如果输入可能极不靠谱可以再额外记录边的编号比较“来的边编号”而不只比较节点。还有一个容易忽略的点节点权值的读入顺序。有的题目先给权值再给边有的先给边再给权值代码里要把输入顺序和变量对应清楚。这里我按“先读n再读n个权值最后读n-1条边”的常见顺序写。3.2 C完整实现下面这份代码以1号节点作为初始根适用于大多数换根DP题目。核心部分只有两个DFS函数代码量不大但每个赋值语句都对应前面讲过的状态转移。#include bits/stdc.h using namespace std; typedef long long ll; const int maxn 100005; vectorint g[maxn]; ll w[maxn]; ll down[maxn], up[maxn], ans[maxn]; // 第一趟DFS自底向上计算 down[u] void dfs1(int u, int fa) { down[u] w[u]; for (int v : g[u]) { if (v fa) continue; dfs1(v, u); if (down[v] 0) { down[u] down[v]; } } } // 第二趟DFS自顶向下计算 up[v] 和 ans[v] void dfs2(int u, int fa) { for (int v : g[u]) { if (v fa) continue; ll outside ans[u] - max(0LL, down[v]); up[v] max(0LL, outside); ans[v] down[v] up[v]; dfs2(v, u); } } int main() { int n; cin n; for (int i 1; i n; i) { cin w[i]; } for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs1(1, 0); // 根节点没有父方向所以 up[1] 0 up[1] 0; ans[1] down[1]; dfs2(1, 0); ll res LLONG_MIN; for (int i 1; i n; i) { res max(res, ans[i]); } cout res \n; return 0; }这段代码里隐藏着一个很容易被忽视的坑ans[u]必须在dfs2访问到u的时候已经被正确计算。根节点ans在进入dfs2前手动初始化其他节点则是在父节点递归进入前算好。也就是说dfs2里的赋值顺序是“先算v的up和ans再递归进入v”顺序反了结果必然出错。另外要注意max(0LL, down[v])里的0LL。权值可能是负的down[v]也可能是负的如果不加LL后缀在某些编译环境下max模板的类型推导会出问题导致比较结果错误。编译器的隐式转换虽然通常不会报错但这种细节在线上评测时可能害你白交几发WA。3.3 复杂度与空间分析两趟DFS都只遍历了每个节点的邻接边一次每条边在两次DFS中各自被访问两次总复杂度O(n)。up、down、ans数组都是O(n)空间邻接表本身O(n)。整个算法的时间和空间都非常干净10^5级别的数据完全够用10^6级别也仅仅是需要稍微注意一下递归栈深度的问题。如果和暴力做对比暴力的O(n^2)与换根的O(n)在n10^5时差距非常明显。这也正是换根法的意义所在它不改变问题的结构只是用一种聪明的增量更新方式把重复计算全部省掉。4. 现场踩坑记录与问题速查4.1 五个容易翻车的细节换根DP的代码本身不长但真正到了赛场上翻车点特别集中。我把这些年实际调试中遇到的高频问题整理成一个速查表每条都对应过一次真实教训。问题现象原因解决方案递归栈溢出程序运行时崩溃n较大时系统栈不够改用迭代式DFS或在线评测系统里加大栈空间权值相加溢出答案错误数值异常大int存不下较大范围加减全部使用long long重边导致死循环TLE或栈溢出只判断v ! fa不够记录边编号比较进入边的编号第二趟DFS顺序错误子节点答案偏小先递归后更新up先算up[v]和ans[v]再进入v负数分支处理不当答案偏大或偏小max(0, down[v])忘记加括号或类型不匹配统一写成max(0LL, ...)第一条递归栈溢出的问题在n10^5、树退化成链时最容易触发。我个人的习惯是比赛环境允许的情况下使用ulimit -s unlimited调整栈大小或者直接把DFS改成手工栈。手工栈写法虽然代码长一点但胜在稳定不会因为评测环境差异出现莫名崩溃。第二条溢出问题很多人会忽略尤其是题目给的权值范围看起来不大时。假设每个节点权值最大10^9n为10^5那么一个连通块的总和理论上可以到10^14这已经远远超出int的表示范围。不要再问为什么int WA这个坑真的太常见了。4.2 调试与验证技巧换根DP的调试最有效的方式是“对拍小数据”。先写一个O(n^2)的暴力版本枚举每个点作为根做一次不含换根优化的DFS算出每个点的答案再跑换根版本对比两边的ans数组是否完全一致。n取20左右随机生成多组树和权值一旦发现不一致立刻输出每个点的down、up、ans以及暴力版本对应值一目了然。我通常还会在纸上手推一个简单例子。比如一棵链状的树三个节点1-2-3权值分别是5、-10、20。第一次DFS后down[3]20down[2]-10max(0,20)10down[1]5max(0,10)15。但注意以2号节点为根时它可以选择同时连上1号和3号得分是-1052015以3号为根时可以连到2再连到1得分20-10515。再看换根结果ans[1]15ans[2]down[2]up[2]10max(0,15-10)15ans[3]down[3]up[3]20max(0,15-max(0,10))25这里需要仔细演算如果up[3]算出的outside是ans[2]-max(0,down[3])15-20-5所以up[3]0ans[3]20。但以3为根时明明可以包含整条链15分问题出在题目模型里“子图必须连通”而负权重可以砍掉20已经是3向下最多收益若再连父方向-105反而亏所以最大仍是20。这个例子恰好说明max(0, outside)的正确性。这种小例子多推几个之后状态定义里的细节就会变得特别清晰。我强烈建议初学者不要直接看大代码而是先在纸上把链、星形、二叉树的典型结构都过一遍。4.3 换根法的拓展场景这套“两趟DFS”的框架并不只适用于“最大连通子图得分”很多树上问题都能套。最常见的是经典题“求树上所有节点到其他节点的距离之和”第一趟DFS算出每个节点子树内的节点数和子树内距离和第二趟DFS利用父节点信息推导子节点的总距离。状态定义变了但“先向下后向上”的结构完全一致。还有“树的最大独立集换根版本”“树上带权路径最大值”“每个点作为根时删掉某些边后的直径问题”等本质上都是同一个套路。学习换根法最赚的一点就是你不需要为每个新题重新发明框架只需要改掉状态定义和那一两个转移方程就能快速适配。如果题目要求输出每个节点的ans而不是全局最大值代码几乎不用变只要在循环里逐项输出即可。如果题目要求取模注意减法时要先加模数再取模避免负数结果。5. 写在最后的一点个人体会换根法这个技巧看起来是“树形DP第二次DFS”但真正难的地方不在代码而在于你能不能想清楚换根的那条边两侧哪些信息被复用了哪些信息需要重新计算。我印象最深的一次调试就是第二趟DFS里把父方向贡献算错导致整条链上一半节点的答案都小了一块。后来我习惯在做这类题之前先画一棵带权树手动把第一次DFS的down和第二次DFS的up都填出来再和代码输出对比。对于刚接触换根法的朋友我建议按这个顺序练习先从“树上距离和”这种经典题入手把两趟DFS的感觉建立出来再回到“最大连通子图得分”这种带正负权值的题体会max(0, ...)的作用最后再挑战带限制的组合类问题。等你的状态定义和转移方程能在脑子里自然转起来换根法就会变成你手里非常顺手的图论工具。