这道题乍一看像是“又一道树形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 暴力方案的时间成本
我们先具体感受一下暴力为什么不行。假设n=10^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]初始化为0，ans[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; vector<int> 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)在n=10^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, ...) |
第一条递归栈溢出的问题，在n=10^5、树退化成链时最容易触发。我个人的习惯是，比赛环境允许的情况下使用ulimit -s unlimited调整栈大小，或者直接把DFS改成手工栈。手工栈写法虽然代码长一点，但胜在稳定，不会因为评测环境差异出现莫名崩溃。
第二条溢出问题很多人会忽略，尤其是题目给的权值范围看起来不大时。假设每个节点权值最大10^9，n为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]=20，down[2]=-10+max(0,20)=10，down[1]=5+max(0,10)=15。但注意，以2号节点为根时，它可以选择同时连上1号和3号，得分是-10+5+20=15；以3号为根时，可以连到2再连到1，得分20-10+5=15。再看换根结果：ans[1]=15，ans[2]=down[2]+up[2]=10+max(0,15-10)=15，ans[3]=down[3]+up[3]=20+max(0,15-max(0,10))=25？这里需要仔细演算，如果up[3]算出的outside是ans[2]-max(0,down[3])=15-20=-5，所以up[3]=0，ans[3]=20。但以3为根时明明可以包含整条链15分？问题出在题目模型里“子图必须连通”而负权重可以砍掉，20已经是3向下最多收益，若再连父方向-10+5反而亏，所以最大仍是20。这个例子恰好说明max(0, outside)的正确性。
这种小例子多推几个之后，状态定义里的细节就会变得特别清晰。我强烈建议初学者不要直接看大代码，而是先在纸上把链、星形、二叉树的典型结构都过一遍。
4.3 换根法的拓展场景
这套“两趟DFS”的框架并不只适用于“最大连通子图得分”，很多树上问题都能套。最常见的是经典题“求树上所有节点到其他节点的距离之和”：第一趟DFS算出每个节点子树内的节点数和子树内距离和，第二趟DFS利用父节点信息推导子节点的总距离。状态定义变了，但“先向下后向上”的结构完全一致。
还有“树的最大独立集换根版本”“树上带权路径最大值”“每个点作为根时删掉某些边后的直径问题”等，本质上都是同一个套路。学习换根法最赚的一点就是：你不需要为每个新题重新发明框架，只需要改掉状态定义和那一两个转移方程，就能快速适配。
如果题目要求输出每个节点的ans而不是全局最大值，代码几乎不用变，只要在循环里逐项输出即可。如果题目要求取模，注意减法时要先加模数再取模，避免负数结果。
5. 写在最后的一点个人体会
换根法这个技巧看起来是“树形DP+第二次DFS”，但真正难的地方不在代码，而在于你能不能想清楚换根的那条边两侧，哪些信息被复用了，哪些信息需要重新计算。我印象最深的一次调试，就是第二趟DFS里把父方向贡献算错，导致整条链上一半节点的答案都小了一块。后来我习惯在做这类题之前，先画一棵带权树，手动把第一次DFS的down和第二次DFS的up都填出来，再和代码输出对比。
对于刚接触换根法的朋友，我建议按这个顺序练习：先从“树上距离和”这种经典题入手，把两趟DFS的感觉建立出来；再回到“最大连通子图得分”这种带正负权值的题，体会max(0, ...)的作用；最后再挑战带限制的组合类问题。等你的状态定义和转移方程能在脑子里自然转起来，换根法就会变成你手里非常顺手的图论工具。
