周恰恰先把结论放在前面：P1122「最大子树和」是一道非常经典的树形DP入门题，题目本身不复杂，但它非常适合练“怎么把树上问题拆成子问题”的思维方式。我第一次刷到这个题号的时候，以为就是个搜索题，把整棵树各种删，看哪个结果大，结果越写越乱。后来想明白一个关键点：这题本质上是让你在一棵带权树上找一个连通点集，让点权和最大，跟一维数组里的最大子段和是同一个味道，只是从数组挪到了树上。如果你正在准备CSP/NOIP，或者刚开始接触树形DP，这道题很值得认真推一遍，推完以后很多树形DP的题你都会觉得亲切不少。
1. 从最大子段和说起：P1122到底在求什么
1.1 题面里最容易被忽略的连通性限制
题目给出一棵有 n 个节点、n-1 条边的树，每个节点带一个权值，权值可正可负。你可以删除一些节点，但删除一个节点后，和它相连的边也会一起消失。题目要求最后剩下的节点仍然构成一棵树，也就是剩下的点必须连通。这个“连通”限制是整个DP能不能成立的前提，也是最容易被理解偏差的地方。
我第一次读题时，脑子里想的是“删掉所有负权点不就行了”。但仔细一想不对，因为负权点可能夹在两个正权块中间。比如一棵链状的树：节点1权值为10，节点2权值为-5，节点3权值为10。如果你把节点2删掉，节点1和节点3就不连通了，剩下的点只有10或者10，不可能得到15。如果你想要15，就必须把中间那个-5也一起保留下来，虽然它是负的，但它是连接两个正权块的“桥”。
所以这题不能单纯删负权，而是要在一个连通点集上做选择。想清楚这一点后，问题就变成了：在一棵树上找一个连通块，使得块内点权和最大。这个表述很重要，后文所有DP设计都围绕它展开。
1.2 一维最大子段和的树形翻版
如果你写过最大子段和，应该记得那个经典DP：
code复制dp[i] = max(nums[i], dp[i-1] + nums[i])
意思是：以第 i 个元素结尾的连续段，要么只选自己，要么把前面最合适的段接上。这个思路的关键在于，通过“结尾元素”固定了区间的右端点，把“区间连续”这个约束转化成了状态的一部分。
P1122 和它非常像。数组里选连续段，树上选连通块，差别只是“连续”的形式不同：数组靠下标相邻，树靠边相连。树形DP要做的，就是模仿一维DP的状态设计，找一个“固定点”来锚定整个连通块。在一维数组里锚点是区间端点，在树上锚点就是连通块中深度最浅的那个节点。
这个类比不是随便说说的。理解了最大子段和，再看P1122的转移式，你会发现它们的结构一模一样：都是“只选自己”和“把子结构的正收益接上”两种选择。
1.3 指定根不代表答案一定包含根
树本身是无根树，但做树形DP必须有一个递归入口，所以我们一般约定：把1号节点当作根，通过父亲-孩子关系来组织整棵树。注意，这里只是“约定”了一个根，不代表答案里一定包含1号节点。
很多新手会直接输出dp[1]，因为树形DP从1开始递归，感觉答案应该在根上。但实际上，最优连通块可能完全在1号节点的某个子树内部，甚至可能不包含1号节点。比如一棵链：1-2-3，权值分别是-100、1、2。以1为根，dp[3]=2，dp[2]=1+max(0,2)=3，dp[1]=-100+max(0,3)=-97。真正的答案是3，对应连通块{2,3}，它不包含1。
这就是为什么最后答案要取所有dp[u]的最大值，而不是只看根节点的dp值。后面写代码的时候，这一点会直接体现在答案统计上。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 状态定义是树形DP的命门：为什么必须有“包含u”
2.1 如果dp[u]不要求包含u，转移会非常尴尬
先看一个容易掉进去的坑：有人会把状态定义成“dp[u]表示u的子树中最大的连通块权值和，但u本身不一定要选”。这个定义听起来也没问题，但它会让转移变得很难写。
假设u有三个儿子a、b、c，每个儿子的子树里都有一个最优连通块。因为u可以不选，这些儿子块之间没有公共连接点，你根本不知道该怎么把它们拼起来。你只能说“取每个儿子子树的最大值”，但这样得到的答案可能来自a的儿子块，也可能来自b的儿子块，它们互相之间是不连通的。如果题目要求最后剩下的点必须连通，那这种情况就不合法。
更麻烦的是，即使u被选了，如果某个儿子块不包含那个儿子，那u和这个儿子块之间可能也没有边直接相连，连通性又断掉了。所以状态里必须明确“当前连通块是否经过了u”这个信息。标准解法就是强制u必须被选，让u成为连接父亲和各儿子块的中心枢纽。
2.2 包含u的好处：儿子块被整体抽象成一个数字
我们定义：
code复制dp[u] = 以u为根的子树内，选出的连通块必须包含u，且所有点都在u的子树内，此时能得到的最大权值和
这里“所有点都在u的子树内”是树形DP的自然范围，因为递归划分了子树。“必须包含u”是连通的关键，因为一旦包含u，u就可以作为连接父节点和子树的桥梁。
转移式很干净：
code复制dp[u] = w[u] + sum_{v是u的儿子} max(0, dp[v])
为什么这样写？因为u一旦被选中，对于每个儿子v，它只有两条路：
- 把v子树里包含v的最大连通块接上来，也就是在u和v之间保留这条边，贡献dp[v]；
- 把v的整棵子树剪掉，贡献0。
你当然希望挑大的那个，所以每个儿子贡献max(0, dp[v])。把所有儿子贡献加上，再加上u自己的权值，就是dp[u]。这本质上是在每个儿子节点上做一次“要不要接入”的贪心决策，而子问题之间互不影响，因为树的分支结构天然保证了独立性。
2.3 边界：负权节点可能在dp里出现正值
这里有一个特别容易被误解的地方：dp[v]是正数，不代表v的权值一定是正的。它只代表“包含v的子树连通块”整体是赚的。
举个例子。设某个节点v权值为-3，它有一个儿子x权值为10。那么dp[x]=10，dp[v]=-3+max(0,10)=7。虽然v本身是负的，但为了能连到x，v必须被选，最终包含v的块还是正的。所以转移式里用的是max(0, dp[v])，而不是max(0, w[v])。这两个差别非常大：后者做的是“只看当前节点”的贪心，会直接把v丢掉，从而也丢掉了整棵正收益子树。
想明白这一点，你就能理解为什么答案可以接受一个负权节点被保留在连通块里。它不是累赘，而是通往更大收益的必经之路。
3. 实现中容易翻车的几个细节
3.1 无向图递归必须传fa
题目给的是无向树，我们建图时会同时把u->v和v->u两条边都加进去。递归时如果不记录父节点，从u访问v后，下一层又从v访问u，就会无限递归，或者至少造成大量重复计算。
标准写法是在dfs参数里加一个fa：
cpp复制void dfs(int u, int fa) {
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
// 处理子节点贡献
}
}
这个fa参数在树链很深的极端情况下尤其重要。没有它，你的程序大概率会在递归边界上摔跟头。
3.2 答案初始化的玄学
很多人做完DP之后，习惯把答案变量初始化成0，因为觉得“最大值至少是0”。但P1122的节点权值可以是负数，而且题目要求最后必须留下至少一个节点。考虑极端情况：整棵树所有权值都是负的，这时候最优解不是删光，而是选一个权值最大的点单独作为连通块。如果答案初始化成0，最终输出会变成0，显然是错的。
正确做法是初始化成极小值，比如LLONG_MIN，然后在每次算出dp[u]后用ans = max(ans, dp[u])更新。这样即使所有权值都是负数，ans也能正确取到最大的那个负数。
3.3 递归写法与爆栈隐患
P1122的n范围我记得大约是16000，递归深度最多也就16000，在主流评测环境下完全不会爆栈，所以不需要额外处理。但如果你以后接触到的题目n是1e5甚至2e5，并且树会退化成一条链，就要警惕递归深度问题了。C++默认栈空间通常几MB到十几MB，2e5层递归在某些评测机上可能会出问题。
有两个应对方向：一是用编译器指令手动扩栈（但依赖平台），二是把DFS改成显式栈的迭代写法。对于P1122这种入门题，递归写法完全够用，但心里要有这个意识，别形成“树形DP一定可以无脑递归”的习惯。
4. 参考代码与一次完整的手算推演
4.1 可直接提交的C++17代码
下面这份代码是我个人比较习惯的写法，注释也标注了关键决策点。
cpp复制#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> w;
vector<vector<int>> g;
vector<ll> dp;
ll ans;
void dfs(int u, int fa) {
dp[u] = w[u]; // 至少保留u自己
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
if (dp[v] > 0) dp[u] += dp[v]; // 赚的子树接上
}
ans = max(ans, dp[u]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
w.assign(n + 1, 0);
g.assign(n + 1, vector<int>());
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);
}
dp.assign(n + 1, 0);
ans = LLONG_MIN;
dfs(1, 0);
cout << ans << '\n';
return 0;
}
有个实现小坑说一下：如果用C++的lambda递归，auto dfs = [&](int u, int fa){ dfs(v, u); }这样写是编译不过的，因为lambda在自身内部还没定义完。用function<void(int,int)>包一层可以解决，或者像我上面一样直接写一个普通函数，配合全局变量。对于竞赛代码，普通函数+全局变量反而更省事，不用在lambda捕获列表里绕来绕去。
4.2 自己构造一个用例手算
纸上谈兵不够，我拿一个自己构造的小数据来完整走一遍DP，你看看状态是怎么一步步算出来的。
树的结构如下，根约定为1：
code复制1(-2)
├─ 2(5)
│ ├─ 4(-1)
│ └─ 5(2)
└─ 3(3)
└─ 6(-4)
先看叶子节点：
- dp[4] = -1
- dp[5] = 2
- dp[6] = -4
再看中间节点：
- dp[2] = 5 + max(0, -1) + max(0, 2) = 5 + 0 + 2 = 7
- dp[3] = 3 + max(0, -4) = 3
最后看根：
- dp[1] = -2 + max(0, 7) + max(0, 3) = -2 + 7 + 3 = 8
所以最终ans = max(-1, 2, -4, 7, 3, 8) = 8。
这个8对应哪个连通块？把节点4和6剪掉，剩下的点是1、2、3、5，权值加起来是-2+5+3+2=8，正好和DP结果一致。这个例子也直观体现了负权节点1被保留的原因：它单独看是负的，但它连接了两个正收益分支，整体就赚了。
4.3 用打印dp数组的方式验证
我在实际刷题时，经常会临时加一行输出，把所有节点的dp值打出来：
cpp复制cerr << "dp[" << u << "] = " << dp[u] << '\n';
尤其是在答案和自己预估不一致的时候，这一招比反复读代码高效得多。你可以对照上面手算的dp数组，如果某个节点的值和你算的不一致，顺着递归顺序查，很快就能定位是转移写错还是建图出错。这个小习惯从入门阶段就可以养成，后面做更复杂的树形DP时非常有用。
5. 从P1122出发：几个常见的变体方向
5.1 如果强制包含某个根，输出dp[1]就行
有时候题目会加上一条限制：最后剩下的树必须包含某个指定节点，比如1号节点。这时候不用取max，答案就是dp[1]，因为连通块强制包含了根，根节点的dp值天然覆盖了这种情形。
这个变体看起来只是改一行输出，但它能帮你检验是否真正理解了状态定义。如果题目问“必须包含节点u”，你就以某个确定根做一次DP，然后看dp[u]是否包含所有可能的连通块。注意，如果根不是固定的，u可能不在根的位置，需要以u作为整棵树的根重新做一遍DP，或者用下面的换根思路。
5.2 如果去掉连通限制，题就“退化”了
如果题目改成：删除任意节点，剩余节点不要求连通，只是让剩余权值和最大。那问题瞬间退化成“保留所有正权点”，答案是所有正权值之和，跟树形DP没有关系了。之所以P1122值得做，正是因为它有“最终必须连通”这一条限制，才逼着你用树的结构来组织DP。很多人会忽略这一点，把它当成“删点”问题想，越想越绕。
下次看到类似题目，第一反应先确认连通性要求。这个条件直接决定了问题的复杂度和算法选择。
5.3 换根DP：当每个节点都要当根时
P1122只要求全世界最大，因此跑一遍以1为根的DP，然后对dp数组取max就够了。但有些题目会问：“对每个节点作为根，分别求最大子树和”。如果你对每个点都重新做一遍树形DP，总复杂度是O(n^2)，n一大会超时。
这时就要用换根DP（也叫二次扫描）：第一遍DFS自底向上求dp[u]；第二遍DFS自顶向下计算“以u为根”的完整答案，转移时把父节点的贡献也纳入“子树”的概念里。核心是把反向的那部分贡献重新计算出来，类似“把父节点当作一个特殊儿子”。
P1122是理解换根DP最好的跳板。如果你已经能熟练写出这题的DP，换根的思想会更容易接受：状态还是那个状态，只是每个节点多了一条来自“新根”方向的边。
5.4 更大的树形DP世界：从这题走出第一条路
树形DP里还有一堆常见模型，比如树上最大独立集、树上背包、树的直径、树上染色问题等等。它们大多数都延续了同一种思考模式：选一个根，把无根树转化成有根树；状态定义围绕“当前节点是否被选中”、“子树内需要满足什么条件”展开；转移时只考虑直接儿子，保证子问题互不干扰。
P1122给我的最大收获，不是记住了dp[u] = w[u] + sum(max(0, dp[v]))这个公式，而是学会了“用状态把连通性约束锚定住”的思路。以后遇到树上连通块相关的问题，我都会先问自己：如果我把某个节点固定为连通块的一部分，问题是否能被拆成若干个互不影响的子问题？如果能，那么树形DP大概率走得通。
多说一句：不管做什么树形DP，我建议你把样例或者自己构造的小数据跑一遍，把dp数组打印出来看看，这样你对状态定义的理解会一下子踏实很多。P1122作为第一道树形DP，很值得老老实实做一次这个动作。