动态规划 · HTML
数学 / 逻辑形态
root 树后 postorder。dp[u][s] 表示 u 子树在 u 处于状态 s 时的答案；对每个 child v，将 dp[v][*] 按父子兼容规则 fold 进 u。
识别信号
- 输入是树或可任选根的无环连通图。
- 删除父边后各子树条件独立。
- 节点选择会约束父子或相邻节点。
- 父节点只需每个子树的小摘要。
- 答案涉及树上选择、覆盖、路径或计数。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 一般图有环 | 子问题不会因一条父边而独立；需图 DP、树分解或别的算法。 |
| 只求高度/总和 | 简单递归聚合即可，不必引入多个 DP 状态。 |
| 路径可跨两个子树却只返回单一全局答案 | 父节点通常需区分向上可延伸值与子树内部最优。 |
核心不变量
dfs(u,parent) 返回 u 子树在每个边界状态下的准确最优值；不同 child 子树仅通过 u 相互作用，因此可逐个合并。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 节点 u、父节点 parent 与 u 的有限边界模式；可有全局答案和向上返回摘要两类量。 |
| Transition | postorder 得到所有 child 状态后，按 u 的每种模式选择兼容 child 状态并求和/取极值。 |
| Frontier / order | 以任意根展开的 DFS 后序；parent 参数阻止沿无向边返回。 |
Python 骨架
def max_non_adjacent(tree, values, root=0):
if not tree:
return 0
def dfs(u, parent):
skip, take = 0, values[u]
for v in tree[u]:
if v == parent: continue
child_skip, child_take = dfs(v, u)
take += child_skip
skip += max(child_skip, child_take)
return skip, take
return max(dfs(root, -1))
正确性思路
- 叶节点的 skip=0、take=value 正确。
- 固定 u 是否选择后，不同子树独立；take 强制 child skip，skip 允许 child 最优二选一。
- 归纳得每个返回状态最优，根无父约束故取两态最大。
复杂度
| Time | Space | Parameters |
|---|
| O(n·q²) 一般状态兼容；固定少量状态常为 O(n) | O(n) 递归栈/状态 | n 为节点数，q 为每节点状态数。 |
边界条件
- 空树
- 单节点
- 负权时允许全不选
- 无向边防回父
- 递归深度
- 森林需虚根或逐组件
错误模式
| Pattern | Why it fails / fix |
|---|
| 只返回一个值 | 父节点对 child 的需求取决于自身模式；必须返回边界条件下的多个值。 |
| 无向树不跳过 parent | 递归会来回循环。 |
| 把全局路径与向上路径混为一谈 | 跨两个 child 的最优路径不能整体继续向父延伸。 |
| 默认根具有特殊语义 | 无根树算法应说明结果是否与任选根无关。 |
选择与排除规则
- 切断父边后判断子树是否独立。
- 状态只编码父节点未来需要的边界信息。
- 区分向上返回值与子树内部全局答案。
- 深树用迭代 postorder 防栈溢出。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 选择两个叶子得 7。 |
| Setup | 根权 5，两个叶子权 4 与 3，相邻节点不能同时选。 |
| Trace | 根 take=5；根 skip=max(0,4)+max(0,3)=7。 |
Recall prompts
我的补充