2023 年天梯赛 L3-2 挂着完美树这个名字当年赛场上把这题放最后做的人不少都是冲着它来的。L3 段位的题有个共同特点代码量不大但状态设计一旦想岔后面怎么调都是错的。这题的核心就两个词——树形DP和01最大/小价值听着玄其实拆开看就是把选或不选这个二值决策挂在树上再让每个节点替自己的子树做一次最优汇报。如果你正在准备 pta 天梯赛或者刚接触树形DP不知道状态怎么下手这篇东西应该能帮你把这题从头到尾捋一遍。我会先把模型抽象清楚再讲状态为什么这么定义、转移方程怎么推、最大价值和最小价值之间到底差了什么最后把代码完整给你包括容易翻车的迭代写法和树上背包的复杂度证明。整篇按能直接抄作业的标准来写读完你可以自己建一组数据验证。1. 把完美树还原成一个可计算的模型1.1 题意重述剥掉外壳之后剩下什么先把题面的装饰剥掉。树上每个点有一个权值你要给每个点做一个点亮 / 不点亮的二选一决策约束是任意一条边的两个端点不能同时被点亮也就是被点亮的点两两不相邻。满足这个约束的染色方案题面叫它完美本质就是图论里的独立集。目标是在所有完美方案里让被点亮节点的权值和最大。我用一个具象的说法帮你建立直觉想象这棵树是一张组织架构图每个节点代表一个项目组权值是它能带来的收益。规则是有直接上下级关系的两个组不能同时启动否则资源冲突问你怎么选组能让总收益最高。这个不能同时启动就是独立集约束一点不抽象。为什么题目要包装成完美树我的理解是出题人希望你不被完美这个词吓到而是自己去发现约束其实就是独立集。赛场上很多人卡住不是因为不会树形DP而是卡在完美两个字上总以为还有什么额外的全局条件没读懂。先做一次语义平移把自然语言翻译成图论术语是解这类题的第一步往往也是最重要的一步。需要说明的是我这里是基于题目骨架抽象出的核心模型。原题可能在外围叠加了颜色、代价、奇偶性之类的设定但只要你发现约束落在父子关系上、决策是二值、目标是极值这三个特征接下来的 DP 设计方法是完全通用的。1.2 数据范围决定了你必须往 DP 上想假设 n 能到 1e5 甚至更大权值能到 1e9甚至负数。这两个数字直接把暴力枚举和状态压缩的路堵死了n 个节点每个点 2 种状态总方案数 2^nn40 都跑不动更别说 1e5。权值到 1e9路径和可能到 1e14int必炸全程long long是硬要求。树结构没有环天然满足无后效性这是 DP 能用的大前提。树上做 DP 的复杂度目标通常是 O(n)因为每条边只会被访问常数次。如果你写出来的做法是 O(n^2) 甚至更高先别急着下结论看看是不是把某个本该 O(1) 的合并写成了线性扫描。树形DP 的入门题几乎都是 O(n)只有加上了个数限制这类额外维度才会升到 O(n^2)后面第 4 节会专门讲这个拐点。1.3 为什么贪心在这里会失效我见过不少人第一反应是每个点单独看正权就选。这是错的。举个最小的反例一条链 a—b权值分别是 5 和 6。如果各自贪心两个都选但它们是相邻的违反约束只能选一个。局部最优不等于全局最优因为一个点的选择会直接改变邻居的可选空间决策之间有依赖。这种依赖在树上表现为父子的选择互相排斥必须用 DP 把两种可能都记下来而不是当场做决定。这一点想通了状态设计就是水到渠成的事。2. dp[u][0] 和 dp[u][1] 到底在记录什么2.1 状态定义把最优子结构落到每个点上树形DP 的精髓是只考虑以 u 为根的子树假设子树外面的世界已经被处理干净问这棵子树内部能贡献的最优值是多少。但光有 u 不够因为 u 的选择会影响它的父亲所以要把 u 的两种状态分别记录dp[u][0]在 u 的子树内且u 不被点亮时能取得的最大权值和。dp[u][1]在 u 的子树内且u 被点亮时能取得的最大权值和。这就是01的含义——每个节点维护两个值对应二值决策的两个分支。为什么必须两个都存因为父亲需要知道如果我不选儿子随便如果我选儿子必须不选。如果你只存一个最优值当父亲需要特定约束时就没有备选答案可用了。树形DP 存两状态本质上是给父亲留两个接口而不是替父亲做决定。2.2 转移方程是怎么一步步推出来的先说 u 被点亮的情况。既然 u 亮了所有儿子 v 都不能亮那么每个儿子只能贡献它不亮的最优值dp[v][0]。加上 u 自己的权值dp[u][1] w[u] Σ dp[v][0] (对所有儿子 v)再说 u 不亮的情况。u 不亮儿子就自由了可以亮也可以不亮各自取两种里更大的那个dp[u][0] Σ max(dp[v][0], dp[v][1]) (对所有儿子 v)边界叶子节点没有儿子求和为空所以dp[leaf][0] 0dp[leaf][1] w[leaf]。最终答案就是max(dp[1][0], dp[1][1])因为根节点没有父亲约束两种状态都合法。这里有个容易被忽略的细节u 不被点亮时我们没有给 u 加上任何权值因为它的贡献是 0。如果权值允许为负那不选反而成为一种收益转移照旧成立不需要特别处理这一点比很多人想的要省事。2.3 最大价值与最小价值其实只差一个负号题面常常会问两种东西最大权值和或者最小权值和。很多同学会写两份代码这是浪费。把所有权值取负最大权独立集就变成了最小权独立集的相反数。设取负后的最大值为 M那么原问题的最小值就是 -M。原因很朴素对每个可行方案取负前后它的权值和刚好相差一个负号取最大值再取负就等于在原来的方案集合里取最小值。不过这个对偶有个坑如果你要求必须至少选一个点取负之后不能直接套。因为原问题最大值允许全不选和为 0取负后 0 变成了最大值候选会把真正的正收益方案压下去。遇到必须选这类附加条件时老老实实改初始值和转移方向别偷懒用取负的技巧。我一般会写两套初始化求最大值时dp[leaf][0]0, dp[leaf][1]w求最小值时dp[leaf][0]0, dp[leaf][1]w但转移里把max换成min同时加入一个不可达的哨兵值防止误选。2.4 状态定义里最容易犯的三个错第一把子树范围搞错。dp[u]永远只描述 u 的子树不要掺入兄弟或祖先的信息否则状态就带记忆了转移会变得无法递归。第二忘了 u 不选时儿子是可以选的。我见过有人写dp[u][0] Σ dp[v][0]这就默认了父亲不选儿子也不选答案会系统性偏小。正确写法一定是max(dp[v][0], dp[v][1])。第三权值为负时想当然地认为不选更优。如果约束允许确实不选更优但你不能在转移里手动判断应该让max自己去比。任何我觉得这里应该取哪个的直觉都要交给转移方程去验证而不是提前写死在代码里。3. 代码落地从建树到跑通一个完整样例3.1 建图和后序遍历的两种写法树用邻接表存无向边双向加。DP 的顺序要求处理 u 时它的所有儿子都已经处理完也就是自底向上。最常见的写法是递归 DFSdfs(u, fa)里先把儿子递归完再算自己的 dp。递归代码短但 n 到 1e5 甚至 2e5 时链状数据会把系统栈压爆这个坑我在实测里踩过不止一次。替代方案有两种。一种是把递归改成显式栈稍微繁琐另一种更讨巧——用 BFS 求出遍历序然后倒着扫这个序列做 DP。很多人以为必须严格后序其实只要保证儿子在序列里排在父亲后面倒序处理就总能先算完儿子。BFS 序天然满足这个性质因为儿子一定比父亲先入队、位置更靠后。// 递归版主逻辑 void dfs(int u, int fa) { dp[u][0] 0; dp[u][1] w[u]; for (int v : g[u]) { if (v fa) continue; dfs(v, u); dp[u][1] dp[v][0]; dp[u][0] max(dp[v][0], dp[v][1]); } }3.2 完整代码与逐行说明#include bits/stdc.h using namespace std; const int MAXN 200005; int n; long long w[MAXN]; vectorint g[MAXN]; long long dp[MAXN][2]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); 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); } // BFS 求遍历序 vectorint order; vectorint parent(n 1, 0); queueint q; q.push(1); parent[1] -1; while (!q.empty()) { int u q.front(); q.pop(); order.push_back(u); for (int v : g[u]) { if (v parent[u]) continue; parent[v] u; q.push(v); } } // 倒序做树形 DP for (int i (int)order.size() - 1; i 0; i--) { int u order[i]; dp[u][0] 0; dp[u][1] w[u]; for (int v : g[u]) { if (v parent[u]) continue; dp[u][1] dp[v][0]; dp[u][0] max(dp[v][0], dp[v][1]); } } cout max(dp[1][0], dp[1][1]) \n; return 0; }几个点单独拎出来说。dp数组开long long权值累加不会溢出但前提是你没在中途做过int类型的中间变量。parent[1] -1是为了让根节点没有父亲这个跳过项用 0 也行只要节点编号从 1 开始就不会冲突。倒序 DP 里对每个 u 先重置 dp 再累加顺序不能反。3.3 手算一棵小树验证正确性给一棵 4 个节点的树1 是根儿子是 2 和 33 的儿子是 4。权值是 w[1]3, w[2]4, w[3]5, w[4]6。叶子 4dp[4][0]0, dp[4][1]6。 节点 3dp[3][1] 5 dp[4][0] 5dp[3][0] max(0,6) 6。 节点 2dp[2][0]0, dp[2][1]4。 根 1dp[1][1] 3 dp[2][0] dp[3][0] 3 0 6 9dp[1][0] max(0,4) max(6,5) 4 6 10。答案 max(9,10)10对应选 {2,3}2 不选时它自己贡献 0但 2 被选贡献 4这里 dp[1][0] 选了 2 和 3 的组合。手算能对上说明转移是对的。每次写完树形DP拿一棵五个点以内的小树手推一遍比调半天代码高效得多。4. 进阶加上恰好选 k 个会难在哪4.1 状态多了一维难度立刻上一个台阶基础版是 O(n) 的那 L3 难度从哪来很常见的一个加强是在完美约束下恰好点亮 k 个点求此时的最大权值和。这时候状态要多一维dp0[u][j]u 子树内恰好选 j 个点且 u 不选的最大值。dp1[u][j]u 子树内恰好选 j 个点且 u 选中的最大值。转移时把儿子的背包和父亲的背包做一次卷积式合并。这也是树上背包的标准套路和普通背包的区别在于合并的双方各是一棵子树物品数量由子树大小决定。4.2 复杂度为什么是 O(n²) 而不是 O(n³)这是这题最值得讲清楚的地方。合并 u 和儿子 v 时双重循环的上界分别是sz[u]已经合并过的部分和sz[v]增量代价约sz[u] * sz[v]。关键在于每一对节点 (x, y)恰好会在它们的 LCA 处被合并计算一次。把所有这些成对贡献加起来正好是 C(n,2) 量级也就是 O(n²)。所以整棵树跑下来是 O(n²)不是 O(n³)。如果你不小心把内层循环也写成从 0 到 n那复杂度就退化成了 O(n³)n3000 就超时。做法是按当前已合并的子树大小限制循环上界很多模板只写sz[u] sz[v]却忘了限制循环这是最隐蔽的 TLE 来源之一。const long long NEG LLONG_MIN / 4; int sz[MAXN]; vectorlong long f0[MAXN], f1[MAXN]; void dfs(int u, int fa) { sz[u] 1; f0[u].assign(2, NEG); // 索引 0..1实际只用 [0..sz[u]] f1[u].assign(2, NEG); f0[u][0] 0; f1[u][1] w[u]; for (int v : g[u]) { if (v fa) continue; dfs(v, u); int old sz[u], nw sz[v]; vectorlong long n0(old nw 1, NEG); vectorlong long n1(old nw 1, NEG); for (int i 0; i old; i) { for (int j 0; j nw; j) { if (f0[u][i] NEG max(f0[v][j], f1[v][j]) NEG) n0[i j] max(n0[i j], f0[u][i] max(f0[v][j], f1[v][j])); if (f1[u][i] NEG f0[v][j] NEG) n1[i j] max(n1[i j], f1[u][i] f0[v][j]); } } sz[u] sz[v]; f0[u] move(n0); f1[u] move(n1); } }4.3 实现上的几个硬性约束第一NEG要取一个足够小但不至于溢出的值。常用LLONG_MIN/4或-1e18配合long long加减不会溢出。第二合并时先存到新数组n0/n1再赋值回f0[u]/f1[u]否则会边读边写结果乱掉。我见过有人直接原地更新答案时对时错。第三恰好 k 个和至多 k 个的写法不同。如果是至多k 个最后在f0[1]和f1[1]里取j k的最大值即可如果是恰好就只能取j k而且要注意初始状态下很多格子是不可达的NEG别把 NEG 当成答案输出。输出的如果是 NEG说明该状态不可达要能识别出来而不是傻乎乎打印一个巨大负数。第四当 k 很小比如 k 100而 n 很大时可以用滚动方式把每个节点的数组长度压到min(sz[u], k) 1能省下大量时间和空间。这个优化在 n1e5、k100 的场景下几乎是必需的。5. 常见问题排查与实战心得5.1 问题速查表现象可能原因处理办法答案系统性偏小u 不选时错误地写成Σ dp[v][0]改成Σ max(dp[v][0], dp[v][1])大数出现负数或溢出全程用了int权值、dp、中间变量统一long long段错误 / 栈溢出递归深度等于 n链状数据爆栈改 BFS 序倒推或显式栈树上背包超时内层循环没按sz限制循环上界改成当前已合并子树大小答案是巨大负数输出了不可达状态判断是否为 NEG 或改用至多 k 的写法遍历顺序出错用了 BFS 正序保证儿子先于父亲处理倒序即可5.2 对拍是性价比最高的调试手段树形DP 一旦写错靠肉眼看代码很难定位。我的习惯是写一份暴力搜索对小树枚举所有 2^n 种染色方案逐一检查约束并记录最优值然后让暴力和 DP 在同一组随机数据上对比。n 控制在 12 以内随机生成几千组只要有一组不一致就打印下来手推。这套流程能揪出九成以上的转移错误。// 暴力枚举所有子集检查独立性取最大权 // 复杂度 O(2^n * n)仅用于 n 15 的对拍另外提醒一句随机数据不要只生成随机树还要专门生成链、菊花、完全二叉这三种极端结构。链考验深度菊花考验宽度完全二叉考验合并边界很多 bug 只在这三种形态下暴露。5.3 几句掏心窝的经验第一先把状态的含义用一句话写下来贴在屏幕上。比如dp[u][1] 表示 u 亮时子树最优写代码时对照这句话检查每一行比事后 debug 省时间。第二树形DP 的模板骨架高度固定建树 → 定序 → 倒推 → 合并 → 输出。你练熟一套骨架遇到新题只是换转移和状态维度不会慌。第三遇到最大 / 最小两种问法先想清楚能不能用取负转化不能转化就说明有额外约束老老实实写第二套初始化。第四比赛里如果 n 允许递归别犹豫直接用 DFS代码短出错少只有在不确定数据规模时才上迭代版。别为了炫技在简单题上写复杂实现能过样例和极限数据的才是好代码。这套思路不只适用于完美树这一道题凡是树上二值决策 父子约束 全局极值的题都是同一个模子。你要是把这篇里的模型和代码跑一遍再自己改几个约束条件试试树形DP 这一关基本就算过了。