数据结构与算法 / 系统课时
在树上汇总子树最优状态
在树上汇总子树最优状态
树形 DP 的核心不是“把数组 DP 搬到树上”,而是让每个节点只向父节点汇报少量足够的信息。以父子节点不能同时选择为例,只需维护“选当前节点”和“不选当前节点”两种子树最优值,再在后序遍历中合并孩子结果。
学习目标
- 根据父子冲突约束为每个节点设计两类 DP 状态
- 用后序遍历从孩子状态计算父节点状态
- 实现树形 DP,并理解为什么根节点只需比较两种最终状态
把父节点真正需要的信息留下
假设每个树节点都有一个权值,要求选择若干节点,使任意父子节点不能同时被选,并让权值总和最大。对某个节点 u,父节点不需要知道它的子树中具体选了哪些节点,只需要知道两种结果:
take[u]:选择u时,u的整棵子树能取得的最大权值skip[u]:不选择u时,u的整棵子树能取得的最大权值
这两个状态恰好对应父节点下一步决策所需的信息。如果父节点被选,那么孩子必须走 skip;如果父节点不选,每个孩子就可以在自己的 take 和 skip 中取更大值。

后序遍历就是计算顺序
设节点 u 的权值为 value[u],孩子集合为 children(u)。如果选择 u,所有孩子都不能选,因此:
take[u] = value[u] + sum(skip[v])
如果不选择 u,每个孩子可以独立选择更优状态,因此:
skip[u] = sum(max(take[v], skip[v]))
这里必须先得到所有孩子的状态,才能计算父节点,所以天然使用后序遍历:先递归处理子树,再处理当前节点。树形 DP 常见的“递归返回多个值”,本质就是把子树压缩成父节点真正需要的状态摘要。
用一个完整示例计算最优值
下面的二叉树对应权值结构:根节点 3 的左孩子为 2、右孩子为 3;左孩子还有右子节点 3,右孩子还有右子节点 1。父子不能同时选择。
from dataclasses import dataclass
from typing import Optional
@dataclass
class TreeNode:
value: int
left: Optional['TreeNode'] = None
right: Optional['TreeNode'] = None
def best_subtree(node: Optional[TreeNode]) -> tuple[int, int]:
if node is None:
return 0, 0
left_take, left_skip = best_subtree(node.left)
right_take, right_skip = best_subtree(node.right)
# 选择当前节点时,两个孩子都必须不选。
take = node.value + left_skip + right_skip
# 不选当前节点时,每个孩子都可以独立取更优状态。
skip = max(left_take, left_skip) + max(right_take, right_skip)
return take, skip
def max_weight(root: Optional[TreeNode]) -> int:
take, skip = best_subtree(root)
return max(take, skip)
if __name__ == '__main__':
root = TreeNode(
3,
left=TreeNode(2, right=TreeNode(3)),
right=TreeNode(3, right=TreeNode(1)),
)
print(max_weight(root))预期输出
7结果 7 可以由选择根节点 3、左下节点 3 和右下节点 1 得到。注意代码从未枚举“所有合法节点集合”,而是在每个节点处只保留两种最优摘要,因此避免了指数级组合搜索。
从二叉树推广到任意树
二叉树只是最容易写代码的形式。对任意多叉树,转移并没有改变:take[u] 仍然累加所有孩子的 skip,skip[u] 仍然累加每个孩子两种状态的较大值。只要树没有环,每条边在 DFS 中处理常数次,总时间复杂度为 O(n)。
状态本身只需每个节点两个值,若递归时即时返回而不额外保存整张表,额外空间主要来自递归栈,最坏为 O(h),其中 h 是树高;退化成链时可达到 O(n)。
判断树形 DP 状态是否够用
设计树形 DP 时,可以从“父节点为了做决策,究竟需要知道子树的哪些信息”出发,而不是先想数组下标。父子冲突问题只需要“选/不选”两态;如果约束变成“最多选一个孩子”“选择节点后距离两层内都不能选”等,状态就要增加能够描述这些边界条件的信息。
一个好的树形 DP 状态应当满足:孩子处理完后可以独立压缩成少量状态,父节点只依赖这些状态完成合并。只要这个条件成立,后序遍历就能把全树问题变成一次自底向上的局部汇总。