说到树形DP，我估计只要搞过算法竞赛的朋友，十有八九都是从洛谷的P1352《没有上司的舞会》开始的。这道题算是树形动态规划的经典敲门砖，也是很多学校集训队拿来给新人讲树上状态转移的第一道题。别看它题面短、数据范围也不算大，里面藏着的“选或不选”状态设计思路，几乎能套用到后面你能见到的所有树上DP问题里。
我当年第一次做这道题的时候，其实连“树形DP”这个名字都没听过。当时只知道普通线性DP，觉得换个结构就不会写了。后来把这道题彻底想明白之后，才意识到树形DP的核心并不是什么高深的数学技巧，而是先把树建好，再用递归把状态一层层从叶子推到根。这个思路通了，之后遇到再复杂的树上问题，至少不会不知道从哪下手。
这篇文章我就把P1352从读题到建图，再到状态设计和代码实现，完整拆开讲一遍。包括当时我自己踩过的坑、网上题解里没细说的那些转移细节，以及为什么很多人的写法明明逻辑对，却总在边界上出问题。
1. 先弄懂题目在说什么
1.1 题目背景和输入输出
P1352的题面讲的是一个公司要开舞会，员工之间有上下级关系。每个人如果参加了舞会，就能获得一个快乐指数，但有一个规则：一个人的直接上司如果来了，这个人就不能来。反过来说，如果这个人来了，他的直接上司就不能来。题目要求的是，在遵守这个规则的前提下，整个舞会能获得的最大快乐指数总和。
输入格式上，第一行给一个正整数n，表示员工人数。接下来n行，每行一个整数，表示第i号员工的快乐指数。再接下来是若干行，每行两个整数l和k，表示k是l的直接上司。输入以“0 0”结束。员工的编号从1到n，而且题目保证这个上下级关系构成的是一棵树，不是一张复杂的图。
这里有个容易看漏的细节：员工编号和树节点的对应关系，完全由后面的边决定。很多人一开始会想当然地认为编号1就是根，其实不一定。比如题目样例里，几组“l k”关系读完以后，根节点是那个没有被别人当成下属的节点。这个根节点得自己找，通常用入度来判断。
1.2 为什么线性DP在这里不管用
如果你做过最长上升子序列或者背包问题，可能会习惯性去想：能不能把所有员工排成一个序列，然后从左到右DP？在P1352里这种思路行不通。因为员工的上下级关系是树状的，每个人是否参加舞会，只受他的直接上司影响，而直接上司又受他自己的上司影响。这种依赖关系不是沿着一条线性序列传递的，而是像树根一样，一层层扩散出去的。
换句话说，这题天然适合“从下往上汇总信息”。一个节点的状态，需要由它所有子节点的状态共同决定。只有等子节点算完了，父节点才能算。这种“先算子树，再算父节点”的顺序，正好是后序遍历的顺序，也正好是递归天然的执行顺序。
我见过不少初学者问：能不能用BFS或者拓扑排序来做？说实话，如果你把树按层序处理好，再用逆序的方式做，也不是完全不行，但代码写起来会比递归麻烦很多，而且容易在父子状态的传递上绕晕。树形DP最正统、也最好理解的方式，就是DFS配合记忆化或者直接递归传递状态。
2. 状态设计与状态转移推演
2.1 二维状态的定义
做DP的第一步永远是定义状态。P1352的状态设计其实很标准：用dp[u][0]表示以u为根的子树里，当u不参加舞会时，能得到的最大快乐值；用dp[u][1]表示当u参加舞会时，以u为根的子树能得到的最大快乐值。
很多人会问：为什么只分0和1两种状态？因为题目里每个员工只有两种选择：去或者不去。而且他的选择只会影响他直接上司和直接下属，不会跨层影响。比如u的父亲和u的儿子之间并没有直接约束关系，所以子树的答案只需要把自己这个节点的选择情况告诉父节点就够了。这就是二维状态刚好够用的原因。
这里需要特别强调：dp[u][1]这个状态虽然叫“u参加”，但它表示的是整棵以u为根的子树的整体收益，不是只有u一个人的收益。很多初学者把状态理解成“单点选或不选的快乐值”，这样推下去就会漏掉子树内部已经累加好的那些最优解。
2.2 状态转移方程的推导
我们先看u参加的情况。既然u要参加，那它的直接下属v就不能参加。所以对于每一个子节点v，我们只能取dp[v][0]这个状态。于是：
dp[u][1] = happy[u] + sum(dp[v][0])，对所有v是u的直接子节点成立。
再看u不参加的情况。u不参加，它的子节点v可以选择参加，也可以选择不参加。因为规则只限制“上司参加时下属不能参加”，上司不参加并不会强制下属必须做什么。所以对于每个子节点v，我们应该取这两者中较大的那个：
dp[u][0] = sum(max(dp[v][0], dp[v][1]))。
这里有个非常容易踩的坑：很多人会把dp[u][0]直接写成sum(dp[v][1])，觉得“上司不去，下属就该去”。这不对，下属去不去要看他自己哪种选择收益更大，完全可能下属自己也不想去，因为他的下属还可能给他带来更大的收益约束。所以必须取最大值，而不是无条件选1状态。
2.3 答案从哪来
最终的快乐值最大值，翻译成树上语言，就是整棵树的根节点root，它参加或不参加的最大值。所以答案应该是：
ans = max(dp[root][0], dp[root][1])。
这里也经常有人问：为什么不能把所有节点的max(dp[u][0], dp[u][1])加在一起？因为dp[u][0]和dp[u][1]本身就是以u为根的子树的整体结果，它已经包括了所有后代节点的最优选择。如果再把每个节点的值加一遍，等于重复计算了好多遍子树的贡献。这是概念理解上的偏差，不是代码bug。
好，到这里为止，状态和转移方程已经完整了。剩下的问题就是怎么用代码把这个递归过程写出来，以及怎么写才对、怎么写不容易错。
3. 代码实现：从记忆化搜索到递归DP
3.1 邻接表建树
要实现树形DP，第一步肯定是把输入里的上下级关系变成程序能用的树结构。多数情况我推荐用邻接表，也就是vector存每个节点的孩子列表。因为在DP的时候，我们只需要从父节点去访问子节点，不太需要反向访问。
建图的核心代码很简单：
vector<int> tree[MAXN]; bool hasParent[MAXN]; for (int i = 1; i <= n; i++) { cin >> l >> k; if (l == 0 && k == 0) break; tree[k].push_back(l); hasParent[l] = true; }然后找根的时候，只需要遍历一遍hasParent数组，找到那个没有任何人把它当下属的节点就是根：
int root = 1; for (int i = 1; i <= n; i++) { if (!hasParent[i]) { root = i; break; } }这里建议用hasParent数组，而不是每次临时判断某个节点是否出现过。原因很简单：输入不是按照编号顺序给的，你无法保证第一个读到的节点就是根，也不能保证边的关系是“先父后子”。用数组标记是最稳的，复杂度是O(n)，完全够用。
3.2 DFS版树形DP核心代码
递归实现树形DP，代码量很少，但逻辑要清晰。先看完整版：
void dfs(int u) { dp[u][1] = happy[u]; dp[u][0] = 0; for (int v : tree[u]) { dfs(v); dp[u][1] += dp[v][0]; dp[u][0] += max(dp[v][0], dp[v][1]); } }调用时，从root出发：
dfs(root); cout << max(dp[root][0], dp[root][1]) << endl;这段代码看起来只有几行，但我建议你先自己手推一遍，确保理解每一行是在做什么。
第一行dp[u][1] = happy[u]是在初始化。因为u要参加舞会，至少它自己的快乐指数是可以直接算进去的。后面在枚举孩子时，dp[u][1]不断累加dp[v][0]，最终才变成整棵子树选u时的最大值。
dp[u][0] = 0则是因为u不参加时，自己的快乐指数不能算，初始为0。后面每处理完一个孩子v，就把以v为根子树的最好结果累加进来。
3.3 为什么先处理子节点再累加
很多人第一次写这段代码时会很困惑：为什么dfs(v)要写在累加之前？因为父节点的状态依赖子节点的状态，这是递归的天然逻辑。你必须先完整算出以v为根的子树的dp值，返回到当前这一层之后，dp[v][0]和dp[v][1]才是有效数据，才能被父节点拿去用。
如果顺序写反了，先加再dfs(v)，那加进去的就是dp[v]的旧值，很可能是全0或者垃圾值，答案必然错误。这个错误不太容易通过编译发现，因为程序不会报错，只会给你一个看起来莫名其妙的结果。
我遇到过有朋友把这段代码用全局变量简化，觉得“反正递归返回前会更新”，结果在多个测试样例下忽对忽错，最后排查了半天，才发现是某个分支提前返回导致没有执行dfs。所以，我的建议是：用最朴素的写法，每个节点都先遍历完整棵子树，再做状态累加，不要试图搞什么骚操作。
除了C++，用Python写也完全可以。核心逻辑一脉相承，就是建图时用列表存孩子，递归时注意Python默认递归深度限制。大部分题目的n都在几千到几万这个量级，如果树的形态比较深，直接用递归可能爆栈，那就需要手动改递归深度或者换成迭代式DFS。用Python刷题的同学一定要记住这个坑。
4. 手把手推样例：搞明白转移过程
4.1 样例数据和建图
光看公式不够，我们拿一套简单的数据手推一遍。比如n=3，快乐指数分别是2、3、1，关系是2号是1号的上司，3号是1号的上司。等等，这样说有点抽象。换个更常见的样例：
- 员工1的快乐值是2
- 员工2的快乐值是3
- 员工3的快乐值是1
- 边：2 1，表示2的上司是1
- 边：3 1，表示3的上司是1
那根节点就是1，子节点是2和3。散点数据看，1如果去，快乐值2，2和3都不能去，总快乐值就是2。1不去，2和3都可以自己决定，如果2去、3去，总快乐值是3+1=4。如果2去、3不去，总快乐值是3。如果2不去、3去，总快乐值是1。所以最大值显然是4，也就是1不去，2和3都去。
我们用DP推一遍：
先算叶子节点2的dp：
- dp[2][1] = happy[2] = 3
- dp[2][0] = 0
同样，叶子节点3：
- dp[3][1] = happy[3] = 1
- dp[3][0] = 0
再回到根节点1：
- dp[1][1] = happy[1] + dp[2][0] + dp[3][0] = 2 + 0 + 0 = 2
- dp[1][0] = max(dp[2][0], dp[2][1]) + max(dp[3][0], dp[3][1]) = max(0, 3) + max(0, 1) = 3 + 1 = 4
最终答案max(2, 4) = 4。
这个手推过程看起来简单，但很多人就是因为没有亲手动过，所以看代码总觉得“好像懂了”，一变数据就不会。我建议每个初学者至少手推三个不同形态的例子：链状树、满二叉树、星型树。这样才能真正理解为什么递归是从叶子往根计算的。
4.2 自底向上的计算顺序
树形DP的“自底向上”不是靠数组下标顺序实现的，而是靠递归调用栈实现的。在dfs(u)里，我们先用for循环递归处理所有孩子，等for循环结束后，所有孩子的dp值已经计算完成。这时候父节点这层的累加语句才真正被执行。
换句话说，程序的执行顺序是：u进栈，一路向下走到某个叶子节点，叶子节点没有孩子，直接完成自己的dp赋值，然后返回。每返回一层，当前节点就利用刚得到的子节点结果更新自己。这个过程其实就是后序遍历。理解这一点后，以后你遇到树上依赖背包、树上最大独立集、树直径等问题时，都会发现核心骨架是完全一样的。
5. 常见问题、优化与变形
5.1 运行栈溢出与读入优化
P1352的题面通常n最大到6000，在C++里递归深度一般不会超过6000，栈一般是能扛住的。但如果出题人把树构造得特别深，比如n=100000且形成一条链，那么递归深度就可能达到100000层，这时候可能会出现“栈溢出”或者程序异常退出。我在训练赛里就遇到过类似情况，题目和P1352很像，但是n更大，递归直接崩了。
解决办法有几个思路。一是把DFS改成显式的栈模拟，用自底向上或后序遍历的方式遍历树：先按从根开始的顺序把节点进栈，再逆序处理dp。这种方法代码会复杂一些，但能完全避开递归深度限制。二是如果你用的是C++，可以尝试在本地或在线评测系统允许的前提下增大栈空间，但不同评测平台策略不一，不一定有效。最稳妥的还是第一种。
另外，如果n很大，输入量也会变大。C++里建议用快速读入，比如scanf或者自定义read函数，尽量避免用cin在读大量整数时因为同步问题拖慢速度。虽然P1352本身n不大，cin加上关闭同步也够用，但从一开始养成好习惯没坏处。
5.2 空间优化和在一维上做的误区
树形DP经常提到空间优化。严格来说，dp[u][0]和dp[u][1]是每个节点都要存一个值的。你可能会想：能不能只用一个一维数组dp[u]代表“u参加时子树的最大值”，另一个一维数组notDp[u]代表“u不参加时子树的最大值”，这不就省板子了吗？其实本质上还是两个数组，只是命名不同。真正的空间优化思路是，如果遍历完之后父子节点不再被需要，可以只保留正在处理的链路上的信息。但在树的形态下，尤其是递归实现中，若想只开一维数组同时表示选与不选，往往需要更多辅助状态，反而增加理解和调试成本。
我见过有的同学想强行在dp[u]一个数组里同时存两种信息，比如用正数表示选、负数表示不选，实际写下来完全是在给自己挖坑。P1352的数据量其实不需要做这种极端的空间优化，规规矩矩开dp[MAXN][2]就好。
5.3 树形DP扩展：带权最大独立集、树的最小点覆盖等
P1352的状态设计思想，放大了看就是一个“树上带权最大独立集”问题。“独立集”指的是一个点集，里面任意两个点都没有直接边相连。放到这道题里，就是不能同时选直接相连的上司和下属。树的最大带权独立集，恰好就是用同样的状态转移：每个点选或不选，选的时候子节点不能选，不选的时候子节点可任意。
顺着这个思路，你还可以做树的最小点覆盖问题，也就是选出最少的点，使得每条边至少有一个端点被选中。这时状态就要变成“这个节点是否被选中”，转移时要保证每条边都被覆盖。你会发现状态仍然是二维，但转移方程针对不同目标会变。再往后还有树的重心、树的直径、树上背包、换根DP……它们的共同点都是“先处理子树，再用子树信息推父节点”。P1352就是这一整类问题的最小原型。
我个人的建议是，不要仅仅满足于过题。你可以做一张表，把这道题改成不同变式：
- 权重为负数时，节点还一定要选吗？
- 如果n变成100000，链状树怎么办？
- 如果要求输出具体选了哪些人，该怎么做路径回溯？
想清楚这三个问题，你对树形DP的理解会比刷十道类似模板题更深刻。
我自己在做P1352的时候，最大的收获不是学会了一个转移方程，而是明白了“不要急着写代码，先画一棵树，标出每个节点的决策选择，想清楚父节点和子节点之间的约束关系”。很多看似复杂的树形DP，只要把每个节点的状态可能性想全，转移方程其实就呼之欲出了。遇到树上的题，先画图，先想清楚后序遍历的顺序，再动手写代码，基本不会跑偏。这道题值得你多刷几遍，直到能闭着眼把邻接表、根节点查找、DFS状态累加全部写对为止。
