第 103A 章　树形 DP¶

本章配套 2 道例题，见 §例题。前置：DP 入门、树的基础与遍历

树形 DP 的状态载体是子树，转移由孩子的状态合并而来，枚举顺序是后序（孩子先于父亲）。模型本身不难，难的是 Python：

树的高度可以达到 \(n\)，所以树形 DP 在 Python 里绝不能写递归。 setrecursionlimit 只解除软限制，物理栈仍会段错误。

本章给出迭代式后序遍历的通用模板，以及「reversed(BFS 序)」这条更省事的路线。

同源的另外三种形态：区间 DP、状压 DP、DAG 上的 DP。

计数版本：把 \(\min\)/\(\max\) 换成 \(+\) 就是计数 DP，取模的时机与陷阱见 DP 入门 · 计数 DP 与取模。

状态是「某个子树」，转移由孩子的状态合并而来。

\[f[u][\text{状态}] = \text{merge}\big(f[c_1][\cdot],\ f[c_2][\cdot],\ \ldots\big)\]

1　⚠️ Python 必须用迭代，不能递归¶

这是本章最重要的一条工程约束。

\(n \le 2\times10^5\) 的链状树，递归深度就是 \(2\times10^5\)：

做法	结果
直接递归	`RecursionError`（默认上限 1000）
`sys.setrecursionlimit(300000)` + 递归	爆 C 栈，段错误（判题机显示 RE，且没有 traceback）
`threading.stack_size(1<<26)` + 线程内递归	✅ 可行
显式栈的迭代式后序遍历	✅ 推荐，通用姿势

setrecursionlimit 只解除了解释器的软限制，真正的物理限制是线程栈大小。这是 Python 竞赛里最隐蔽的 RE 来源之一——本地小数据全过，判题机上大数据直接段错误。

2　迭代式后序遍历模板¶

# [片段]
# 通用写法：显式栈，用一个标记位区分「进入」与「回溯」
stack = [(root, -1, False)]           # 三元组：结点、父结点、是否处于回溯阶段
while stack:
    u, fa, back = stack.pop()
    if back:
        # 此时 u 的所有孩子都已处理完 —— 在这里做合并
        for c in g[u]:
            if c != fa:               # 无向图里要靠父结点编号挡住「往回走」
                merge(u, c)
    else:
        stack.append((u, fa, True))   # 先压回自己的回溯帧，它会在所有孩子之后被弹出
        for c in g[u]:
            if c != fa:
                stack.append((c, u, False))   # 再压孩子，于是孩子先被处理

更快的写法（当输入直接给出有向父子边时）：只要按 BFS 序遍历一遍，再倒着累加即可——子节点一定排在父节点后面，倒序就是合法的后序：

# [片段]
order = bfs_order(root)               # 一次 BFS 得到层序：父结点一定排在孩子之前
for u in reversed(order):             # 倒序 = 后序，连栈都不用
    merge_into_parent(u)              # 轮到 u 时它的子树已全部合并完毕

这个技巧避免了显式栈的元组打包开销，是树形 DP 在 Python 里的最优形态。 BISHI143 的输入天然给出「\(k\) 是 \(\ell\) 的上司」的有向父子边，正好适用。

3　例题 · BISHI143 没有上司的舞会（较难）¶

题号	题名	难度	题解
BISHI143	没有上司的舞会	较难	题解
LC124	二叉树中的最大路径和	困难	题解

树上最大权独立集：选了某点就不能选它的父亲。\(n \le 2\times10^5\)，\(w_i \in [-128, 127]\)。

两个状态：

\[ \begin{aligned} g[u] &= \text{邀请 } u \text{ 时子树的最大气氛值} = w_u + \sum_{c} f[c] \\ f[u] &= \text{不邀请 } u \text{ 时的最大值} = \sum_{c} \max(g[c],\ f[c]) \end{aligned} \]

答案 \(= \max(g[\text{root}],\ f[\text{root}])\)。

坑：\(w_i\) 可以是负数，所以 \(g[u]\) 不一定优于 \(f[u]\)，不能写成「叶子一定选」的贪心。\(f[u]\) 里对每个孩子取 \(\max(g[c], f[c])\) 而不是 \(g[c]\)，就是因为孩子的权值可能为负、不选反而更好。

题解：solutions/nowcoder/BISHI143/sol.py（已通过官方样例验证）

LC124 二叉树中的最大路径和¶

LC 124. 二叉树中的最大路径和与「树的直径」是同一个骨架，只是把「深度」换成了「权和」：一次后序遍历，每个节点用「左侧最大贡献＋右侧最大贡献＋自身权值」更新全局答案，而返回给父节点的只能是一侧——路径在这个节点拐了弯，就没法再往上延伸了。与直径的差别在于权值可以为负：向上的贡献要写成「子节点返回值与 \(0\) 取大」，让贡献为负的整棵子树直接被舍弃。答案的初值也不能取 \(0\)——全为负数的树上答案就是那个最大的负数，初值取 \(0\) 等于把「一个节点都不选」当成了合法路径，而题面要求路径至少含一个节点。节点数上限 \(3 \times 10^4\)，按本章开头那条纪律，遍历要写成迭代式后序。

4　树形 DP 的常见状态设计¶

问题	状态
最大权独立集	\(f[u][0/1]\)：\(u\) 选 / 不选
树的直径	\(f[u]\) = 从 \(u\) 往下的最长链；答案在每个点合并两条最长链
树上背包（选课）	\(f[u][j]\) = 子树里选 \(j\) 个点。见背包问题 §8
树的重心	\(f[u]\) = 子树大小，重心是 \(\max(\text{最大子树},\ n - size_u)\) 最小的点
换根 DP	两次遍历：先自下而上求子树内答案，再自上而下把「父亲方向」的贡献传下来

5　本章速查¶

形态	状态载体	枚举顺序	「最后一步」是什么
树形 DP	子树	后序（孩子先于父亲）	每个孩子选哪个状态

Python 关键	做法
树形 DP 绝不能递归	迭代后序，或「BFS 序倒序」
`setrecursionlimit` 不够	只解除软限制，物理栈仍会段错误

规模判据	Python
树形 DP \(O(n)\)	\(2\times10^5\) ✅（必须迭代）
树上背包 \(O(n^2)\)	\(n \le 500\) ✅

第 103A 章 树形 DP¶

1 ⚠️ Python 必须用迭代，不能递归¶

2 迭代式后序遍历模板¶

3 例题 · BISHI143 没有上司的舞会（较难）¶