状态定义在树的每个节点上，通过一次 DFS 后序遍历，让子节点的信息先算好，再一层层汇总给父节点。
树形 DP 把动态规划的状态定义在树的每一个节点上——一个节点的最优解，取决于它所有子节点的最优解。这天然对应树的递归结构：用 DFS 从根节点出发，先递归处理完所有子节点（后序遍历），子节点的信息算好之后，再回过头来计算当前节点的答案。11 模块讲过的二叉树遍历，到这里派上了用场。
公司的员工关系构成一棵树（每个员工只有一个直属上司，大老板是根节点）。每个员工有一个"快乐指数"。要邀请一部分员工参加舞会，使得快乐指数总和最大，但有一条限制：如果某个员工来了，他的直属上司就不能来（反之亦然）。这是"树的最大独立集"问题的经典变体——树上任意一条边的两个端点，不能同时被选中。
设 dp[u][1] 表示"以 u 为根的子树中，u 参加舞会"时能达到的最大快乐指数总和；dp[u][0] 表示"u 不参加"时的最大值。转移方程：
| 情况 | 转移方程 | 原因 |
|---|---|---|
| u 参加（dp[u][1]） | value[u] + Σ dp[child][0] | u 参加了，所有孩子都不能参加，只能用孩子"不参加"的值 |
| u 不参加（dp[u][0]） | Σ max(dp[child][0], dp[child][1]) | u 不参加，对孩子没有限制，每个孩子取"参加"和"不参加"里更大的 |
dp[child][0]、dp[child][1] 都已经算好）之后，再用上面的公式计算当前节点的 dp[u][0]、dp[u][1]。6 名员工，快乐指数分别是：1号(老板)=10，2号=5，3号=3，4号=8，5号=2，6号=6；上下级关系：1 是 2、3 的上司，2 是 4、5 的上司，3 是 6 的上司：
| 节点 | dp[u][1]（参加） | dp[u][0]（不参加） | 计算过程 |
|---|---|---|---|
| 4（叶子） | 8 | 0 | 叶子没有孩子，dp[1]=value，dp[0]=0 |
| 5（叶子） | 2 | 0 | 同上 |
| 6（叶子） | 6 | 0 | 同上 |
| 2 | 5 | 10 | dp[1]=5+dp[4][0]+dp[5][0]=5+0+0；dp[0]=max(0,8)+max(0,2)=8+2 |
| 3 | 3 | 6 | dp[1]=3+dp[6][0]=3+0；dp[0]=max(0,6)=6 |
| 1（根） | 26 | 16 | dp[1]=10+dp[2][0]+dp[3][0]=10+10+6=26；dp[0]=max(10,5)+max(6,3)=10+6=16 |
max(dp[1][0], dp[1][1]) = max(16, 26) = 26，在 1 参加时取得。对应的实际方案是：1、4、5、6 号参加，2、3 号不参加——快乐指数总和 10+8+2+6=26。这里有个容易被忽略的细节：1 参加，虽然它的孩子 2、3 不能参加，但"孙子"4、5、6 完全可以参加（因为限制只针对直接的上下级关系）——树形 DP 的 dp[u][1] 用 dp[child][0] 转移，而不是简单地"隔一层选一层"，正确地体现了这一点。| 1 | int value[MAXN], dp[MAXN][2]; // dp[u][0/1]：u 不参加/参加时的最大值 |
| 2 | vector<int> children[MAXN]; // children[u]：u 的所有直接下属 |
| 3 | |
| 4 | void DFS(int u) |
| 5 | { |
| 6 | dp[u][1] = value[u]; // 先假设 u 参加，只算上 u 自己的贡献 |
| 7 | dp[u][0] = 0; |
| 8 | for (int v : children[u]) |
| 9 | { |
| 10 | DFS(v); // ★ 先递归处理孩子，回来后 dp[v][0]、dp[v][1] 才是算好的 |
| 11 | dp[u][1] += dp[v][0]; // u 参加，孩子只能用"不参加"的值 |
| 12 | dp[u][0] += max(dp[v][0], dp[v][1]); // u 不参加，孩子取两者较大值 |
| 13 | } |
| 14 | } |
| 15 | |
| 16 | int MaxHappiness(int root) |
| 17 | { |
| 18 | DFS(root); |
| 19 | return max(dp[root][0], dp[root][1]); |
| 20 | } |
DFS(v) 递归调用先于第 11、12 行对 dp[u] 的更新——函数调用的顺序天然保证了"孩子先算完，父亲才能用它的结果"，不需要像区间 DP 那样手动控制"按什么顺序填表"，DFS 的递归结构自动就是正确的顺序。每个节点、每条边都只会被访问一次，时间复杂度 O(n)，和树的遍历同阶。
DFS 从父节点走向子节点时，子节点的邻居列表里也包含"父节点"这个方向，如果不加判断直接递归，会不停地在父子之间来回递归，永远不会结束。常见解决办法：存图时只保留"父指向子"这一个方向（像本节 children[] 数组那样），或者递归时额外传入 parent 参数，跳过指向父节点的这条边。DFS，把每棵树的根节点各自的 max(dp[root][0], dp[root][1]) 加起来，才是整个森林的答案。1（爷爷）和 4、5、6（孙子）是可以同时参加的。树形 DP 的转移方程 dp[u][1] 只减去了"儿子必须不参加"这一层限制，并没有对"孙子"做任何限制，这正是转移方程设计正确、而不是简单按层交替选择的原因。