1. 从“将功补过”这个标题说起：一道树形DP题的建模思路
第一次看到“将功补过”这四个字，很多人会以为是职场复盘或者人生感悟类的文章，但在算法竞赛的语境里，它其实是一道非常典型的树形DP题目。标题里的“将功补过”四个字，本质上描述的是这样一个场景：某个节点犯了错，需要通过后续的某些操作来弥补，而弥补的过程会影响到整棵树的状态转移。这种“先有过、再补过”的设定，在树形DP里通常体现为状态里带一个“是否已经补过”的维度。
我接触树形DP这些年，发现一个规律：凡是题目名字带点故事感的，往往状态设计才是真正的难点，而不是转移方程本身。因为故事背景会给你一种“好像应该这样做”的直觉，但真正落到代码上，你会发现状态维度少一个就漏解，多一个就爆炸。这道题就是典型代表。
这篇文章我打算把这道题从建模、状态设计、转移推导、边界处理、代码实现到常见坑完整拆一遍。适合已经会写基础树形DP（比如“没有上司的舞会”那种）但一遇到带附加维度的题目就卡壳的读者。如果你连邻接表存树都还不熟，建议先把基础打牢再来看，不然会有点吃力。
提示：本文所有代码均为C++实现，默认使用链式前向星或vector存树，递归写法为主。如果你习惯迭代写法，思路完全一致，只是遍历顺序要自己控制好。
2. “将功补过”到底在描述什么：把故事翻译成状态
2.1 题目场景的合理还原
由于原始项目正文是空的，我需要根据标题和树形DP的常见套路，还原出这道题最可能的样子。结合“将功补过”这个说法，我推测题目大意是这样的：
有一棵以1为根的树，每个节点有一个“错误值”或者“贡献值”。某个节点如果犯了错，它会对它的父节点或者整条祖先链产生负面影响。现在允许你选择某些节点进行“补过”操作，补过之后该节点的负面影响被消除，但补过操作本身有代价，或者会影响到子节点的状态。问在满足某些约束的前提下，最小代价是多少，或者最大收益是多少。
这类题在树形DP里有一个非常经典的变体：每个节点有两个状态，一个是“已经补过”，一个是“还没补过”，而“还没补过”的节点会强制要求它的某个子节点必须补过，或者它的父节点必须补过。这就是“将功补过”四个字在算法层面的真正含义——过和补之间存在依赖关系，这种依赖关系沿着树的边传递。
2.2 为什么不能只用一维状态
很多人第一反应是：设dp[u]表示以u为根的子树的最小代价。然后发现根本转移不下去，因为dp[u]无法表达“u这个节点到底补没补过”。如果u没补过，那么u对父节点的影响还在，父节点在做决策时必须知道这件事；如果u补过了，父节点就可以当无事发生。
所以状态至少是二维的：dp[u][0/1]，其中0表示u没补过，1表示u补过了。但这样还不够，因为“补过”这个操作可能会对子节点提出额外要求。比如题目可能规定：如果u补过了，那么u的所有子节点必须都没补过（因为补过的资源被u占用了）；或者反过来，如果u没补过，那么u至少有一个子节点必须补过（因为要有人来帮u补）。
这就是为什么这道题的状态设计比普通树形DP多一层：你不仅要记录当前节点补没补，还要记录当前节点的子节点们是否满足了某种“补过”的约束。
2.3 状态设计的常见变体对比
我把这类题常见的状态设计整理成一张表，方便你对照自己遇到的题目：
| 状态设计 | 含义 | 适用场景 |
|---|---|---|
| dp[u][0/1] | u没补过/补过 | 最基础版本，补过只影响自身 |
| dp[u][0/1][0/1] | u没补过/补过，且子树中是否有节点补过 | 需要统计子树内补过节点数量 |
| dp[u][0/1/2] | u没补过且无人帮补/u没补过但有人帮补/u补过了 | 补过操作可以来自子节点 |
| dp[u][0/1] + 贪心 | 先假设全不补，再考虑哪些补最划算 | 补过代价与深度相关 |
具体到“将功补过”这个标题，我倾向于第三种：u没补过且没有子节点帮它补、u没补过但有子节点帮它补、u自己补过了。因为“将功补过”强调的就是“功”来自哪里——是自己立功补自己的过，还是别人立功帮你补过。
3. 转移方程的推导：从叶子往上，每一步都要想清楚
3.1 叶子节点的初始化
叶子节点没有子节点，所以它的状态最简单：
dp[u][0]：u没补过，且没有子节点帮它补。因为叶子没有子节点，所以这个状态如果合法，代价就是0；如果不合法（题目要求没补过的节点必须有子节点帮补），那就是无穷大。dp[u][1]：u没补过，但有子节点帮它补。叶子没有子节点，所以这个状态直接是无穷大。dp[u][2]：u自己补过了。代价就是补过操作本身的代价cost[u]。
这里有一个非常容易踩的坑：很多题目里“没补过”本身不是错误，只有“没补过且没人帮补”才是错误。所以dp[u][0]在叶子节点是否合法，完全取决于题目对“过”的定义。如果题目说每个节点都必须最终处于“补过”或者“有人帮补”的状态，那么叶子节点的dp[u][0]就是无穷大。
3.2 非叶子节点的合并逻辑
假设u有若干子节点v1, v2, ..., vk。我们需要把子节点的状态合并上来。合并的时候，对于每个子节点v，它有三种状态可选：dp[v][0]、dp[v][1]、dp[v][2]。但并不是所有组合都合法，因为u的状态会对子节点提出约束。
以dp[u][2]（u自己补过）为例。如果题目规定“u补过之后，子节点不能再补过”，那么对于每个子节点v，只能选dp[v][0]或dp[v][1]，不能选dp[v][2]。如果题目没有这个限制，那三个都能选，取min即可。
再以dp[u][1]（u没补过，但有子节点帮补）为例。这个状态要求至少有一个子节点选择了dp[v][2]（子节点自己补过，从而帮u补）。所以在合并的时候，我们需要记录“是否已经有一个子节点帮了u”。这就是一个典型的背包式合并：先假设所有子节点都不帮u，然后枚举哪一个子节点改成帮u，取最优。
具体写法上，我习惯用一个临时变量f[0/1]表示当前合并到第i个子节点时，是否已经有子节点帮u的最小代价。初始f[0]=0, f[1]=INF。每加入一个子节点v：
new_f[0] = f[0] + min(dp[v][0], dp[v][2]) // 注意这里不能选dp[v][1]，因为v如果没补过但有人帮v补，那v自己没帮u new_f[1] = min(f[1] + min(dp[v][0], dp[v][1], dp[v][2]), f[0] + dp[v][2])这里new_f[1]的第二个转移就是“之前没人帮u，现在让v来帮”。这个转移是整道题的核心，写错一个符号就全盘皆输。
3.3 为什么不能简单取min
我见过很多人写树形DP的时候，直接对子节点所有状态取min然后加起来。这种做法在“没有附加约束”的题目里没问题，但在这道题里会出错。原因很简单：取min会丢失“是否有人帮u”这个信息。你可能选出来的方案里，每个子节点都选了dp[v][0]，结果u没人帮，但dp[u][1]要求必须有人帮，这就矛盾了。
所以正确的做法是：先明确当前节点的状态对子节点提出了什么约束，然后在约束范围内做合并。这也是树形DP从入门到进阶的关键一步——状态不是随便设的，每个状态都对应一组对子节点的约束条件。
4. 代码实现：从递归框架到每一个转移的落地
4.1 存树与递归框架
我用vector存树，递归写法，代码简洁不易出错：
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const long long INF = 1e18; vector<int> g[MAXN]; long long cost[MAXN]; long long dp[MAXN][3]; int n; void dfs(int u, int fa) { // 初始化：先假设u是叶子 dp[u][0] = 0; // 没补过，没人帮 dp[u][1] = INF; // 没补过，有人帮（叶子不可能） dp[u][2] = cost[u]; // 自己补过 for (int v : g[u]) { if (v == fa) continue; dfs(v, u); long long new0 = INF, new1 = INF, new2 = INF; // 计算dp[u][0]：u没补过且没人帮，子节点不能帮u // 子节点可以选dp[v][0]或dp[v][2]，但不能选dp[v][1]（因为v帮不了u） new0 = dp[u][0] + min(dp[v][0], dp[v][2]); // 计算dp[u][1]：u没补过但有人帮 // 情况一：之前已经有人帮，当前v随便选 // 情况二：之前没人帮，当前v必须选dp[v][2]来帮u new1 = min(dp[u][1] + min({dp[v][0], dp[v][1], dp[v][2]}), dp[u][0] + dp[v][2]); // 计算dp[u][2]：u自己补过 // 子节点不能选dp[v][2]（如果题目规定补过资源互斥） // 如果题目没有这个限制，就把dp[v][2]也加进min new2 = dp[u][2] + min(dp[v][0], dp[v][1]); dp[u][0] = new0; dp[u][1] = new1; dp[u][2] = new2; } }这段代码里有一个细节值得展开：为什么dp[u][0]的转移里子节点不能选dp[v][1]？因为dp[v][1]的含义是“v没补过，但v的子节点帮v补了”。注意，帮的是v，不是u。v自己都没补过，它拿什么帮u？所以v对u没有任何帮助，u如果指望v来帮自己，那是不现实的。这个逻辑一定要想清楚，不然转移方程写出来就是错的。
4.2 边界条件与无穷大的处理
无穷大我用了1e18，因为题目里代价可能是1e9级别，节点数1e5，乘起来是1e14，用1e18足够大且不会溢出。但要注意：在加法转移的时候，如果两个INF相加，会溢出成负数。所以严谨的写法应该加一个判断：
long long add(long long a, long long b) { if (a >= INF || b >= INF) return INF; return a + b; }我见过太多人因为INF溢出调了半天，最后发现是INF + INF变成了负数，然后min取到了这个负数，答案就错了。这个坑非常隐蔽，因为小数据根本测不出来。
4.3 根节点的答案选择
递归结束后，答案在根节点1的状态里取。但要注意：根节点没有父节点，所以它不能依赖“父节点帮它补”。也就是说，根节点要么自己补过（dp[1][2]），要么没补过但有人帮（dp[1][1]），不能是dp[1][0]（没补过且没人帮），因为根节点没人帮它。
所以最终答案是min(dp[1][1], dp[1][2])。如果题目允许根节点没补过且没人帮（比如题目说“过”只影响父节点，根节点没有父节点所以无所谓），那dp[1][0]也要纳入考虑。这一点一定要根据题目原文确认，不要想当然。
5. 调试与验证：怎么确认你的转移是对的
5.1 手推小样例
我习惯用一棵三个节点的树来验证：1是根，2和3是1的子节点。给每个节点一个补过代价，然后手动枚举所有补过方案，算出最优值，再和代码跑出来的结果对比。
比如设cost[1]=5, cost[2]=3, cost[3]=4。手动枚举：
- 方案一：1补过，2和3都不补。代价5。此时2和3没补过且没人帮，如果题目要求每个节点都必须补过或有人帮，这个方案不合法。
- 方案二：1不补，2补，3补。代价7。此时1有人帮（2和3都帮了），合法。
- 方案三：1补，2补，3不补。代价8。如果题目允许补过资源互斥，这个方案可能不合法。
把每种方案的合法性和代价列清楚，然后看代码输出是否一致。如果不一致，就单步调试，看是哪个状态的转移出了问题。
5.2 对拍验证
如果题目有暴力做法（比如枚举所有补过集合，判断合法性，取最小代价），那就写一个暴力程序，随机生成小数据，对拍。对拍是发现转移方程错误的最有效手段，没有之一。我调树形DP的题，基本上都是靠对拍找出问题的。
对拍的时候要注意：随机生成的树要覆盖各种形态，包括链、菊花、完全二叉树、随机树。不同形态的树会触发不同的转移路径，链状树容易暴露递归深度问题，菊花树容易暴露合并顺序问题。
5.3 常见错误对照表
| 错误现象 | 可能原因 | 排查方法 |
|---|---|---|
| 答案偏大 | INF溢出成负数被min取到 | 检查加法是否有溢出保护 |
| 答案偏小 | 转移时选了不合法的子节点状态 | 检查每个状态的约束条件 |
| 部分数据错 | 根节点答案选择错误 | 确认根节点是否允许dp[1][0] |
| 递归爆栈 | 树退化成链，递归深度1e5 | 改迭代或手动扩栈 |
| 答案不稳定 | 合并顺序影响结果 | 检查是否用了临时变量，是否原地修改 |
6. 从这道题延伸出去的树形DP通用套路
6.1 状态维度是怎么加上去的
树形DP的状态维度，本质上来自约束条件。每多一个约束，就多一个维度。比如：
- 约束“每个节点补没补” → 加一维0/1
- 约束“子树内补过节点的数量” → 加一维计数
- 约束“当前节点是否被父节点影响” → 加一维0/1
- 约束“当前节点是否被某个子节点影响” → 加一维0/1
“将功补过”这道题同时有“自己补没补”和“有没有人帮”两个约束，所以至少是三维（或者两维加一个合并时的临时状态）。很多人觉得三维DP很吓人，但其实只要把每个维度的含义想清楚，转移方程就是水到渠成的事。
6.2 背包式合并的通用写法
树形DP里，只要涉及“至少选一个”“最多选一个”“恰好选k个”这类约束，基本上都是背包式合并。通用模板是：
// f[j]表示当前已合并的子树中，满足某种条件的方案数/最小代价 // 初始f[0]=0，其他为INF for (每个子节点v) { dfs(v); for (j = 上限; j >= 0; j--) { for (k = 0; k <= j; k++) { f[j] = min(f[j], f[j-k] + dp[v][k]); } } }这道题里，“是否有人帮u”就是一个大小为2的背包，所以合并的时候只需要维护两个值。如果题目变成“至少要有k个子节点帮u”，那背包大小就是k+1，写法完全一样。
6.3 什么时候该用树形DP
不是所有树上的问题都适合树形DP。我判断的标准是：如果问题的最优解可以分解为子树的独立最优解的组合，并且子树之间的影响可以通过有限个状态传递，那就用树形DP。如果子树之间的影响是全局的（比如“整棵树中补过节点总数不超过K”），那可能需要树上背包或者换根DP。
“将功补过”这道题，子树之间的影响仅限于“父节点是否有人帮”，这个信息量很小，所以树形DP非常合适。如果题目改成“整棵树补过节点总数恰好为K”，那就变成树上背包了，状态里还要加一维计数，复杂度也会上去。
7. 一些实战中总结的注意事项
第一，递归深度。如果题目数据范围是1e5，树可能退化成链，递归深度就是1e5，默认栈空间可能不够。我一般会在代码开头加#pragma comment(linker, "/STACK:102400000,102400000")（Windows环境）或者用迭代写法。如果是在线评测系统，最好直接写迭代，省得因为栈溢出莫名其妙RE。
第二，long long的使用。代价和答案都可能超过int范围，所以dp数组和cost数组都用long long。但要注意，long long的INF不要设成0x3f3f3f3f，那个是int级别的，对long long来说太小了。我一般用1e18或者0x3f3f3f3f3f3f3f3f。
第三，多组数据的清空。如果题目有多组测试数据，每次都要把邻接表、dp数组、cost数组清空。我习惯用for(int i=1;i<=n;i++) g[i].clear();而不是memset(g,0,sizeof(g))，因为vector的clear更干净。
第四，状态转移的顺序。在合并子节点的时候，一定要用临时变量存新值，不能原地修改。因为dp[u][1]的转移依赖于旧的dp[u][0]，如果你先更新了dp[u][0]，那dp[u][1]就会用到新值，结果就错了。这个坑我踩过不止一次，后来养成了“先算new，再赋值”的习惯。
第五，根节点的选择。题目一般默认1是根，但有时候根是任意指定的。如果根不固定，那就要考虑换根DP，或者把问题转化成有根树。这道题默认1是根，所以直接dfs(1,0)即可。
第六，补过代价为负数的情况。如果题目允许补过代价为负数（即补过反而赚钱），那就要小心了：这时候“不补”可能不是最优的，因为补了反而更赚。这种情况下，dp的初始化要特别小心，不能简单地把dp[u][0]设成0，因为可能所有节点都补过才是最优的。我遇到过一道类似的题，因为没考虑负代价，WA了整整一页。
8. 写在最后：树形DP的“手感”是怎么练出来的
树形DP这东西，看别人代码觉得很简单，自己写就各种漏状态、漏转移。我刚开始学的时候，一道“没有上司的舞会”写了三遍才过，后来慢慢刷了几十道题，才找到那种“看到题目就知道状态该怎么设”的手感。
我的经验是：每道题做完之后，不要急着下一道，先把状态设计的理由写下来。比如这道“将功补过”，为什么是三维不是两维？因为“有没有人帮”这个信息必须单独记录，不能和“自己补没补”合并。写清楚这个理由，下次遇到类似的题，你就能快速判断该加哪一维。
另外，多画图。把树画出来，把每个节点的状态标在图上，然后手动模拟一遍转移。画着画着，你就会发现哪些状态是多余的，哪些状态是缺失的。这比盯着代码看有效得多。
最后说一句，树形DP的代码量不大，但思维量很大。一道题可能就五六十行代码，但背后的状态设计和转移推导能写满两页纸。所以不要怕慢，慢慢推，推清楚了再写代码，比写完了再调要快得多。
