1. 这道“舞会题”到底在考什么1.1 题目原貌一个“选人名单”问题“没有上司的舞会”是树形DP里最经典的入门题没有之一。我第一次在刷题列表里看到它时以为是个模拟题公司举办年会每个员工有一个欢乐值有人来有人不来要求参会总欢乐值最大但约束很扎心——如果某个员工来参加他的直接上司就不能来反过来如果上司来了直接下属也得待在家里。把题目翻译成数据结构的语言就是公司里的上下级关系是一棵树每个员工是树上节点直属上下级关系就是父子边。每个节点有一个点权欢乐值。我们要从这棵树里选出一个点集使得任何一条边的两个端点不能同时入选目标是让选中节点的点权之和最大。很多题解直接把这题归类为“树形DP”但为什么它天然适配树形DP因为树是连通无环的结构。树的任意两个节点之间只有一条路径删掉某个节点后剩下的部分会分裂成互不影响的连通块也就是子树。这个大前提决定了我们可以把问题拆分成若干独立子问题这是动态规划能成立的根本原因。1.2 剥开背景它等价于树上的最大权独立集如果你接触过图论会发现“任选一条边都不能同时选两个端点”这个约束就是独立集的定义。这题严格来说是在树这种特殊结构上求最大权独立集。这里有个值得注意的点如果你的图是一张普通图最大权独立集是NP难问题暴力枚举所有选法就是O(2^N)基本别想做大。但树让问题变简单了树上不存在环所以每个节点的决策只会影响它的孩子和父亲不会出现那种“A影响B、B影响C、C又绕回A”的全局纠缠状态。于是我们可以放心地递归到子树内部求解再把结果一层一层合并回根节点。这也是为什么很多教程会把“没有上司的舞会”和“打家劫舍III”放在一起讲两者本质上都是树上的选择问题状态设计思路完全同构。你把舞会题吃透后面这类树上选点问题都会变得非常顺。1.3 为什么这个模型能把O(2^N)降到O(N)如果不做任何优化直接枚举每个员工来与不来是2^N种方案显然不现实。但树上有一个关键性质对于以u为根的子树无论整棵树其他地方怎么选子树内部的最佳方案只取决于一个条件——u到底来不来。为什么因为u是所有子树的“共同边界”子树内部是否合法以及子树对外部能贡献多少都只通过u这个节点与外界联系。u来则所有直接孩子全被锁死u不来则每个孩子那边可以独立做决定。这个“只依赖父节点状态”的特点让问题具有了最优子结构我们可以把每个节点的子问题定义成两个状态自底向上地合并最终复杂度降到O(N)。2. 状态设计一个人来不来怎么变成两个数字2.1 从“需要子树信息”到定义dp[u][0/1]很多第一次接触树形DP的人会卡在第一步我到底该按什么顺序算是像BFS那样一层一层算还是直接从根一路推下去答案是都不对。因为你站在一个节点做决策时必须提前知道子树内部的情况。比如你很想让某个大老板参加可他一旦参加所有直接下属都不能来而这些下属中可能藏着一大批欢乐值很高的员工。所以你需要先问子树“如果你们那边的根不来能贡献多少”以及“如果你们那边的根来又能贡献多少”拿到这两个数字你才知道怎么选。于是就有了最经典的两个状态dp[u][0]u不参加舞会时以u为根的子树能获得的最大欢乐值。dp[u][1]u参加舞会时以u为根的子树能获得的最大欢乐值。这两个状态覆盖了u的所有可能性不多不少。孩子子树的答案不需要关心u有没有来以外的信息因为u的职业状态就是整棵子树对外界的唯一接口。2.2 转移方程父子之间只有两种交互方式先约定一下符号u是某个节点的编号v是u的孩子。欢乐值记为h[u]。如果u参加那么每个孩子v都被迫不参加所以dp[u][1] h[u] Σ(dp[v][0])如果u不参加那么每个孩子v可以自由选择来或不来取舍时当然选更大的那个dp[u][0] Σ(max(dp[v][0], dp[v][1]))最后整棵树的答案就是根节点两种状态当中的较大值ans max(dp[root][0], dp[root][1])这个方程的核心逻辑就一句话父节点的状态决定了孩子的状态空间但孩子内部怎么选父节点管不着只需要孩子把最优方案报上来。2.3 手算一个三层链看看DP是怎么传递的光看公式可能有点干我拿一个三节点链手算一遍你马上就能体会信息从叶子往根流动的过程。假设A是B的上级B是C的上级欢乐值分别是A10B20C50先处理叶子C。C没有孩子所以dp[C][0] 0C不来dp[C][1] 50C自己来接着处理B。B有两个选择B不来孩子C可以自由来max(0, 50) 50所以dp[B][0] 50。B来欢乐值20孩子C必须不来所以dp[B][1] 20 0 20。然后到了根AA不来孩子B自由取max(20, 50) 50所以dp[A][0] 50。A来欢乐值10孩子B必须不来那B子树最多能给多少注意孩子B不来时B的子树可以贡献50所以dp[A][1] 10 50 60。最后答案取max(50, 60) 60最优方案是A和C一起参加。这个例子特别能说明问题如果你只按“隔层选”的方式贪心AC是60看起来碰巧对了但你把B改成200再算一遍DP会立刻给出正确答案200选B而“隔层选”那种固定节奏就废了。DP不是靠模板而是靠状态自动适配权重变化。3. 建图和找根先把树真正“立”起来3.1 输入到底该怎么读谁是谁的上司题目里最常见的输入格式是第一行N接着N行欢乐值再给N-1行每行两个整数L、K表示K是L的直接上司。这里必须小心不同题目的变量名顺序不太一样但语义都一样左边是下属右边是上级。很多人写错代码不是因为DP方程不会而是在建图这一步把边方向搞反了。建图方式推荐用“有向边”从上司指向下属child[K].push_back(L);这样建图的好处是后面DFS时不需要额外维护一个parent参数因为树的方向已经固定遍历过程中不会出现走回头路的情况。3.2 几种典型建图方式对比如果你用的是无向图把所有边都存成双向也可以但DFS时必须传父节点编号否则会死循环。这种方式更通用适合题目关系不清晰或者图可能不是严格有向树的场景。有向建图在“没有上司的舞会”里更直观代码也更短。还有一种更省事的存法既然每个节点只有一个上司可以开一个fa数组fa[L] K同时用vector存孩子列表。这样既能方便地找根也能方便地DFS。3.3 找根的小技巧与多根情况如果题目没有明说根是谁那就在读入边时用一个布尔数组标记“出现过在下属位置”的节点最后扫描一遍所有节点没被标记过的就是根bool isChild[N 1] {false}; for (int i 0; i N - 1; i) { int L, K; cin L K; child[K].push_back(L); isChild[L] true; } int root -1; for (int i 1; i N; i) { if (!isChild[i]) { root i; break; } }但这个做法隐含一个假设整棵树只有一个根。实际比赛或面试中有时会给“森林”也就是多个根节点。这时候有两种处理方式对每个根分别做一次DFS最后把答案加起来。更统一的做法是设一个虚拟根0让所有真实根都成为它的孩子然后从0开始做DFS。注意虚拟根的欢乐值要设成0避免污染答案。我一般推荐先判断题目是一棵树还是森林别上来就默认只有一个根尤其是你从OJ上备数据时常常会踩到多根的情况。4. 递归实现让信息从叶子往上走4.1 Python核心代码与注释先给一份可以直接跑通的Python版本。说实话Python写树形DP很舒服但你必须先把递归深度调大否则数据一长就RecursionError。import sys sys.setrecursionlimit(1 25) n int(sys.stdin.readline()) happy [0] list(map(int, sys.stdin.readline().split())) children [[] for _ in range(n 1)] is_child [False] * (n 1) for _ in range(n - 1): l, k map(int, sys.stdin.readline().split()) # k 是 l 的直接上司所以把 l 挂到 k 下面 children[k].append(l) is_child[l] True # 找根 root -1 for i in range(1, n 1): if not is_child[i]: root i break dp [[0, 0] for _ in range(n 1)] def dfs(u): # 状态1u来至少先把自己的欢乐值算上 dp[u][1] happy[u] for v in children[u]: dfs(v) dp[u][1] dp[v][0] dp[u][0] max(dp[v][0], dp[v][1]) dfs(root) print(max(dp[root][0], dp[root][1]))代码本身不长但里面有两个关键点第一dfs(v)必须在更新当前节点之前调用这保证了孩子信息先算完第二dp[u][1]初始化成happy[u]dp[u][0]默认是0这两个初值别搞混。4.2 C版本与一个容易忽略的初始化C版本和Python版本思路一模一样只是写法上更啰嗦一点#include bits/stdc.h using namespace std; const int N 6005; int n, root; int happy[N], dp[N][2]; vectorint child[N]; bool isChild[N]; void dfs(int u) { dp[u][1] happy[u]; for (int v : child[u]) { dfs(v); dp[u][1] dp[v][0]; dp[u][0] max(dp[v][0], dp[v][1]); } } int main() { cin n; for (int i 1; i n; i) cin happy[i]; for (int i 1; i n; i) { int l, k; cin l k; child[k].push_back(l); isChild[l] true; } for (int i 1; i n; i) { if (!isChild[i]) root i; } dfs(root); cout max(dp[root][0], dp[root][1]) endl; return 0; }有的同学会把dp数组定义成dp[N][2]后忘了初始化其实全局变量在C里默认是0所以dp[u][0]天然是0。但dp[u][1]必须在每次调用dfs时重新赋成happy[u]不能依赖全局残留值。4.3 复杂度与空间占用这个递归做法的复杂度很清楚每个节点恰好被访问一次每个节点的孩子列表也被完整扫描一次所以时间O(N)。空间上孩子列表、dp数组都是O(N)另外系统递归栈最坏情况下也会到达O(N)。O(N)的复杂度意味着N可以到几十万甚至上百万但这时递归写法就会开始犯嘀咕如果树退化成一条链递归深度就是N栈会爆。这也是我下面要单独讲迭代写法的原因。5. 递归爆栈的替代方案换成循环来跑5.1 什么时候需要担心爆栈假设N100000树是一条从根一路连下去的链。递归版dfs会一层层往下钻C默认栈空间大概8MB左右像这种深递归很容易Segmentation Fault。Python更明显默认递归深度限制只有1000超过直接RecursionError。如果你只在OJ上刷题可能觉得设一个超大setrecursionlimit就够了但某些平台的栈限制很严格递归照样会崩。所以掌握了递归写法之后建议也把迭代写法练一遍不是因为它更高级而是因为它是真正的“兜底方案”。5.2 迭代后序遍历版本第一种迭代写法采用“先根收集后逆序处理”的思路代码非常短。def solve(root): order [] stack [root] # 先做一次迭代DFS得到节点的访问顺序 while stack: u stack.pop() order.append(u) for v in children[u]: stack.append(v) # 逆序遍历保证子节点先于父节点被计算 for u in reversed(order): dp[u][1] happy[u] for v in children[u]: dp[u][1] dp[v][0] dp[u][0] max(dp[v][0], dp[v][1]) return max(dp[root][0], dp[root][1])为什么逆序就能保证孩子在父亲之前算完因为在第一遍DFS时每个父节点被加入到order里的时间一定早于它的所有子孙节点。把order整体反过来之后子孙节点自然排在父节点前面。这个性质在有向树里永远成立不需要额外标记状态。5.3 从叶子往上的“剥洋葱”写法另一种更贴近“自底向上”直觉的写法是用队列不断从叶子向上合并。先统计每个节点的孩子数量把所有叶子节点入队每次处理完叶子就更新它的父亲同时父亲的孩子计数减一等父亲的孩子都处理完了它自己也变成了新的叶子。from collections import deque deg [len(children[i]) for i in range(n 1)] dp [[0, happy[i]] for i in range(n 1)] fa [0] * (n 1) # 读入边时额外记录fa[L] K q deque(i for i in range(1, n 1) if deg[i] 0) while q: u q.popleft() p fa[u] if p: dp[p][1] dp[u][0] dp[p][0] max(dp[u][0], dp[u][1]) deg[p] - 1 if deg[p] 0: q.append(p) print(max(dp[root][0], dp[root][1]))这种写法天然不需要递归适合数据范围很大的场景。但也需要注意一点它要求提前知道每个节点的父节点所以建图时除了children列表外最好再存一个fa数组。两种迭代方法对比下来我个人觉得“先序遍历再逆序处理”更容易记忆代码量也更少“剥洋葱”的思路更直观在某些需要同时处理森林的场景下更顺手。你不需要两个都背但两个都写过一遍对树形DP的理解会明显不一样。6. 实战中常见的三个坑6.1 把边建反了根节点全乱了这个坑我踩过不止一次。题目输入是“L K表示K是L的直接上司”意思是右边的K是老板左边的L是下属。正确写法是child[K].push_back(L)。但很多人看到两个数字后习惯性把第一个当父节点写成了child[L].push_back(K)结果整棵树的方向反了。方向反了之后最典型的症状是你找不到一个“从没当过孩子”的节点或者找到了一个看起来像根的叶子节点但DFS只能访问到一小部分节点答案自然是错的。排查方法很简单输出一下每个节点的孩子列表或者打印一下root是谁再对比输入样例立刻就能发现问题。6.2 欢乐值为负数时max和0不要乱初始化经典题目里没有规定欢乐值只能是正数所有如果某人欢价值是-5你会不会硬着头皮把他加进去dp会自然处理这个问题如果一个节点来参加反而会降低总欢乐值那它的最优方案就是“不来”在状态转移时取max就能排除掉。但要小心一种常见错误有人为了“防止负数影响”在合并时强行把dp[u][0]和dp[u][1]跟0取max比如写成dp[u][0] max(dp[u][0], 0)。这个操作会破坏DP的语义。因为在某种约束下比如父节点必须来而孩子必须不来时孩子的dp[child][0]即使为负你也必须接受这个负值因为那是被父节点锁出来的代价。如果你强行清零就会高估某些受迫方案的欢乐值最后答案可能偏大。6.3 多组测试用例的残留数据很多OJ题面不会只给一组数据而是“第一行是测试组数T”。如果你只顾着写一组数据的代码第二组开始就会受到上一组残留数据的影响children列表没清空isChild数组还是老状态dp数组更是乱七八糟。处理方式有两种。一是每次循环都重新定义局部数组比如C里在while(T--)内部建vectorPython里用列表推导式重新初始化。二是使用全局数组时在每组输入前手动memset或重新赋值。我习惯用局部数组省心还能避免不同组之间不小心串数。6.4 递归深度带来的隐性RE这一点在上面已经提到但值得再强调一次Python的sys.setrecursionlimit(1 25)虽然能解决问题但某些环境的安全递归深度依然有限。如果你在线上笔试系统里遇到RecursionError很可能是这道题的本意就是要你用迭代写法。所以做题先看数据范围N超过10^5时我一般直接上迭代版本不会赌平台给不给面子。7. 从这道题延伸出去的一类树形dp问题7.1 通用套路状态、转移、顺序做完“没有上司的舞会”你应该能从具体题目里提炼出一套通用的树形DP套路而不是只记住一个题。我总结下来的流程是这样的第一明确每个节点可能要面对的全部状态。比如“来/不来”或者“选/不选/选两个”等。状态不必多但必须能覆盖当前节点所有可能的对外影响。第二把状态定义成“以当前节点为根的子树内在当前节点处于该状态时的最优值”。这个定义让你处理孩子时只需要看孩子返回的两个状态。第三写转移时把每个孩子当成一个独立的“候选方案包”当前节点状态确定后每个孩子该贡献什么就贡献什么贡献方式通过max或sum合并到自己的dp里。第四确定遍历顺序绝大多数情况下都是先递归孩子再更新父亲。如果是迭代写法就找一个能保证孩子先于父亲被计算的顺序。这套流程看起来像模板但它不是死记硬背而是从“最优子结构无后效性”两个基本原则直接推出来的结果。7.2 树形背包与更多变体“没有上司的舞会”是树形DP里的地基但只掌握“来/不来”这两种状态还不够。最常见的扩展是加一个“名额限制”的树形背包问题既然公司有预算只能请恰好K个员工那该怎么办这时候dp状态要变成三维dp[u][j][0]表示以u为根的子树里恰好选j个员工且u不参加时的最大欢乐值dp[u][j][1]表示u参加的情况。转移时对每个孩子v做一次类似背包的循环合并选择的员工数量for j from current_选人数量 downto 0: for k in 0..v子树里可选人数量: dp[u][j][1] max(dp[u][j][1], dp[u][j-k][1] dp[v][k][0]) dp[u][j][0] max(dp[u][j][0], dp[u][j-k][0] max(dp[v][k][0], dp[v][k][1]))你仔细看就会发现它的核心还是“父节点来不来决定孩子只能给哪一种状态”这件事只是额外加了一维人数限制。所以把基础版真正理解透扩展版也就没那么难了。7.3 个人建议怎么刷这道题最有收获我给准备刷这道题的朋友一个建议别只写一遍递归版本就翻篇至少再手写一遍迭代版本。写的时候追问自己三个问题第一为什么孩子状态要先于父节点算完第二如果我不用递归只用循环怎么保证顺序第三如果这棵树是一个森林我的代码还能跑出正确答案吗这三个问题覆盖了树形DP的绝大部分考点也顺带帮你理清了图论里“遍历顺序”和“状态依赖”之间的关系。很多人在树形DP上卡住不是不知道转移方程而是没搞懂为什么先DFS孩子再更新父亲以及这个顺序在迭代写法里如何体现。我自己的习惯是每学一个新模型就把它压缩成一句话写进笔记。“没有上司的舞会”这一题后来被我记成了在树上做选择时把“当前节点选/不选”作为dp维度所有孩子像独立背包一样把状态合并上来。等你把这句话用到下一棵树上你会发现它不再是模板而是一种很自然的推导。