01先把问题说具体
树上每个节点有收益,相邻节点不能同时选择,求最大总收益。线性房屋问题变成树后还怎么推?
02一步步得到方法
父节点选择会限制孩子
定义 take[u] 为必须选 u 时子树最优值,skip[u] 为不选 u 时子树最优值。选 u 后孩子不能选,所以 take[u]=value[u]+Σskip[v]。不选 u 时孩子可选可不选,所以 skip[u]=Σmax(take[v],skip[v])。
为什么可以直接把孩子结果相加?树中不同子树之间没有边,给定 u 的选择后,它们独立。一般图里不同分支可能有交叉约束,不能沿同一公式直接相加。
后序保证依赖先完成
先递归所有孩子,取得两个状态,再合成父节点。无向树的邻接表还含父边,要传入 parent 避免回走。代码要求输入确实是一棵树;有环时仅跳父节点不够。
收益允许负数且允许空选择,skip 可为 0,最终取根两状态最大值。若强制至少选一个节点,则要补充状态,避免空选择被误认作合法最优。
状态需要向父节点传递哪些约束
父节点通常不需要知道孩子整个子树的每个选择,只需要知道与父选择相关的几种最优结果。独立集问题用选根与不选根两个状态,正是因为父子不能同时选。
选当前节点时每个孩子只能取不选状态;不选当前节点时,孩子可各取较优状态。子树之间没有额外边,所以这些最优结果可以独立相加;一般图中该独立性可能被环破坏。
03把一个小例子完全算清楚
根 0 收益 5,孩子 1、2 收益 4、3;节点 1 的孩子 3 收益 6。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 叶子 3、2 | 状态 (6,0)、(3,0) | 顺序为选、不选 |
| 节点 1 | take=4,skip=6 | 不选 1 可选 3 |
| 根 0 | take=5+6+0=11;skip=6+3=9 | 最优选 0、3 |
窄屏可左右滑动表格,阅读完整计算与理由。
答案 11,选择根不意味着跳过整个孩子子树,只禁止孩子节点本身。
04为什么这个方法成立
- 叶子状态正确。
- 固定 u 是否选择后,各子树约束独立,且孩子允许状态明确。
- 将各子树的最优合法状态相加,后序归纳得到整树最优。
05把推导翻译成代码
Python · 可独立运行的教学实现
def tree_independent_set(values, edges):
n = len(values)
if n == 0:
return 0
adj = [[] for _ in range(n)]
for u,v in edges:
adj[u].append(v); adj[v].append(u)
def visit(u,parent):
take,skip = values[u],0
for v in adj[u]:
if v == parent:
continue
child_take,child_skip = visit(v,u)
take += child_skip
skip += max(child_take,child_skip)
return take,skip
return max(visit(0,-1))逐个理解关键决定
take += child_skip- 选父只能要求孩子不选,仍可选孙子。
skip += max(child_take,child_skip)- 不同孩子独立选择各自较优状态。
06时间、空间与实现范围
合法 n 节点树,每条边处理常数次,时间 O(n),邻接表 O(n),递归栈 O(h)。
链状大树可能触发 Python 递归深度限制,可改成显式后序;此实现不接受一般有环图或不连通森林。
07改变条件,检查哪里会出错
不选孩子就丢掉整棵孩子子树
skip[v] 仍可能包含孙子等节点的收益。
对有环图直接使用树形相加
子问题可能共享节点或相互约束,简单累加会重复计数或忽略跨边限制。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
星形树根 5、三个叶子各 3,选谁?
需要一点提示
比较 take 与 skip。
查看解析与答案
不选根,选三叶,收益 9。
一条链会退化为哪种问题?
需要一点提示
相邻不能同时选。
查看解析与答案
一维最大不相邻和,树形状态是它的自然推广。
一般图为何不能直接用 DFS 树求?
需要一点提示
DFS 树外仍有边。
查看解析与答案
跨子树边可能连接两个同时被选节点,破坏独立性,必须考虑额外约束。