树形动态规划：从子公司报表到全局最优的层层汇总

可视化演示

交互展示树形动态规划自底向上的状态转移过程，对比最大独立集选/不选策略与换根DP两次DFS方法。

核心概念

首先，我们要明确一个问题：什么是“树形DP”？如果把动态规划比作“填表”，那树形DP就是在一棵倒长的树上填表——每个节点对应一行“小账本”，记录着以它为根的子树能取得的最优值。

在公司场景里，每个部门经理都有一本账本，记录着自己部门能创造的最大利润。这本账本不是凭空写出来的，而是等所有下属先把账本交上来之后，经理结合自己的业绩和下属们的贡献，最终汇总成自己的一页。这里的关键是：子树的账本一旦算好，就不会再变，可以直接被父节点信赖和使用。 这种“先建立子问题的答案，再层层向上”的特性，正是动态规划“最优子结构”在树上的体现。

定义状态时，我们通常用 f[u] 表示以节点 u 为根的子树的最优值。但仅仅一个值往往不够，因为决策的“选择”不同，会影响父亲的计算。于是我们引入多维状态，比如 f[u][0] 和 f[u][1] 分别表示“不选 u”和“选 u”两种情况。

回到公司的场景：集团董事长的账本，是所有子公司账本的“汇总版”。每个子公司的账本又是由它下面的团队账本汇总而来。这种一层层交账本、逐级汇总的过程，正是树形DP的骨架。理解了“子树独立、逐级合并”，你就已经握住了树形DP的钥匙。

后序遍历

在公司例子里，“先收齐下属报表，再汇总自己”这个流程，在计算机科学里对应着树的后序遍历（Post-order Traversal）。后序遍历的规则非常简单：对于任意一个节点，先递归访问它的所有子节点，最后再访问它自己。

为什么必须是后序？假设你是一个部门经理，如果在自己还没搞清楚下属的情况时就先算自己的利润，那一定是瞎猜的——因为你缺少关键信息。信息只能从基层一层层汇报上来。所以，遍历的方向必须是自底向上的。这个方向不是物理空间的方向，而是数据依赖的方向：父节点的答案依赖子节点的答案，因此子节点必须先被计算。

递归实现是后序遍历最自然的写法：

这个递归过程蕴含着典型的分治思想。分治分三步：分解（把整个树拆成若干子树）、解决（递归求解每个子树）、合并（把子树结果组合成父节点的结果）。树形DP就是分治思想在“带最优值计算”场景的延伸——不仅分解，还要记录每个子问题的最优答案。

def dfs(u, parent):    # 先处理所有孩子    for v in children[u]:        if v != parent:            dfs(v, u)            # 此时 v 的子树的答案已经算好，可以合并            dp[u] = combine(dp[u], dp[v])    # 最后计算 u 自身（可选，视问题而定）

状态转移方程设计

有了遍历顺序，下一步就是设计状态转移方程。这是树形DP的灵魂。我们还是回到公司场景：假设集团要在子公司中评选“最佳利润贡献奖”，规则是相邻层级不能同时获奖——因为如果经理和下属同时当选，会让人觉得有徇私嫌疑。这个规则下的最大利润和，就是经典的树的最大独立集（Maximum Independent Set on Tree）问题。

定义两个状态：

• f[u][0] 表示以 u 为根的子树中，不选 u 时能获得的最大利润；

• f[u][1] 表示以 u 为根的子树中，选 u 时能获得的最大利润。

如何转移？如果选了 u，由于相邻节点不能同选，它的孩子 v 只能选择“不选”状态，即 f[v][0]。反过来，如果不选 u，它的孩子 v 就可以自由选择——选或不选哪个利润大就选哪个，即 max(f[v][0], f[v][1])。这个“自由选择”的本质就是子树的独立性：每个孩子的决策互不影响，只和自己的子树有关。

这个状态转移方程的价值在于它把“相邻互斥”的约束变成了清晰的两条公式。在公司场景里，实施“相邻不能同时获奖”后，董事长只需看两本最终账本——“我上台领奖的利润”和“我不上台领奖的利润”——挑一个大的即可。你可能会想：那要是“父子不能同时选，但可以隔代选”呢？放心，隔代由 f[v][0] 的下一层 f[v][1] 照顾到了，因为 f[v][0] 本身就是孙子们自由选择后的最优值。这就是状态设计的美妙：它把复杂的跨层约束压缩进了状态里。

经典问题

掌握了基础的选/不选模型，我们看它的两个重要变形。第一个是树形背包问题（Tree Knapsack）。想象公司有一笔培训预算，每个部门有一个培训项目，需要先报上级项目再报下级项目（依赖关系构成树），每个项目有成本和收益，在预算内选项目使收益最大——这就是“树上的01背包”。状态定义类似：f[u][j] 表示以 u 为根的子树，花费恰好为 j 的预算时能获得的最大收益。转移时对每个孩子 v 枚举它分配的预算 k：

第二个变形是最小覆盖集：选择最少的节点，使每条边至少有一个端点被选中——可以理解为给每条“上下级关系”装一个监控（选中的节点就是监控点），目标是监控最少。它的状态也只需要选/不选两个维度：

总结规律：树形DP的题目千变万化，但状态设计的思路高度一致——分析每个节点的决策选项，把每个选项变成一个状态维度，然后后序遍历合并孩子状态。无论是独立集、背包、覆盖还是路径问题，都在这个框架内。

实现方式

树形DP的代码实现主要有两种写法：记忆化递归和迭代（自底向上）。记忆化递归是最直观的写法——递归函数天然对应树的深度优先遍历，加一个 memo 数组记录已经算过的子树状态，避免重复计算。

在实际比赛中，如果树的规模很大（比如 n=10^5），递归的深度可能达到 O(n)，在 Python 中容易触发栈溢出（RecursionError）。这时可以考虑迭代实现：先用一次 DFS（或者用栈模拟）收集节点的后序遍历顺序，然后按这个顺序逆序处理——先处理深的节点，再处理浅的节点。这样就不用递归了。

举个例子，迭代处理独立集问题：先用栈模拟后序遍历，得到 order 列表，里面叶子在前、根在后；然后逆序遍历 order，对每个节点 u，将它贡献的状态加入父节点：

复杂度分析：无论是递归还是迭代，每个节点和边都只访问一次，时间复杂度都是 O(n)；空间复杂度也是 O(n)（存储 dp 数组和递归栈/显式栈）。数学上，树有 n 个节点、n-1 条边，每次操作 O(1)，所以总复杂度 O(n)。相比之下，标准 DP 面对的是二维表（O(n^2) 空间），而树形DP利用树的分治结构，把空间压到了一维数组——这就是树这种独特结构带来的红利。

order = []stack = [(root, 0)]while stack:    u, state = stack.pop()    if state == 0:        stack.append((u, 1))        for v in children[u]:            stack.append((v, 0))    else:        order.append(u) # 逆序处理：叶子先算for u in reversed(order):    if u == root:        continue    # 把 dp[u] 合并进父节点 dp[parent[u]]    ...

换根DP

前面讲的树形DP都固定了一个根。但有些问题需要把每个节点都当作根来求答案——比如“以每个城市为总部，配送成本最小是多少”。如果对每个节点都重新跑一次树形DP，复杂度是 O(n²)，当 n=10^5 时无法承受。换根DP（Rerooting DP）用两次 DFS 解决了这个问题，把复杂度降为 O(n)。

核心思路是：第一次 DFS，任选一个根（比如 1），计算 dp[u]——以 u 为根的子树内的答案。第二次 DFS，从根出发，用一个“来自父亲的信息” up[u]，把每个节点的答案“换”成以它为根时的全局答案。这就像公司总部从北京搬到上海：不需要重新跑遍所有子公司问一遍数据，只需要知道——原来总部在北京时的总数据，减去上海子公司的局部数据，再加上上海作为总部后其他部分的新贡献。

转移公式（以求到所有节点距离和为例）：设 sz[v] 为 v 的子树大小，ans[v] = ans[u] + n - 2 * sz[v]。意思是：根从 u 换到 v 时，v 的子树里的节点距离变近了 1（一共 sz[v] 个），而其他节点距离变远了 1（一共 n - sz[v] 个），所以总距离变化量为：

第一次 DFS 从下往上收集子树信息，第二次 DFS 从上往下推导换根后的答案。这种“先自底向上、再自顶向下”的模式，让每个节点都以 O(1) 的代价成为“新根”。换根DP揭示了一个深刻思想：树的答案可以在节点之间“滚动传播”，而不必每次从头算起。

def dfs1(u, parent):    sz[u] = 1    for v in children[u]:        if v != parent:            dfs1(v, u)            sz[u] += sz[v]            dp[u] += dp[v] + sz[v]  # 到子树所有节点的距离和 def dfs2(u, parent):    for v in children[u]:        if v != parent:            ans[v] = ans[u] + n - 2 * sz[v]            dfs2(v, u)

实战案例与应用

最后，我们把视角拉回真实世界。树形DP在工业界和算法竞赛中都有广泛应用：

树的直径（Tree Diameter）：找出树上距离最远的一对节点。可以用两次 BFS/DFS，也可以用树形DP。状态设计为 d1[u]（从 u 向下走的最长链）和 d2[u]（次长链），直径就是 max(d1[u] + d2[u])。这相当于在公司里找“两个相隔最远的基层员工”，策略是经过每个部门经理时，把最长延伸到两棵子树的两条链拼起来试试。

资源分配：在视频CDN网络中，边缘节点组成一棵树，要在一些节点上部署缓存，让每个用户到最近缓存的距离之和最短——这是树形DP的经典落地；在游戏技能树中，玩家要在有限技能点下最大化战力，每项技能有前置技能，这正是树形背包的直接应用。凡是“树形依赖 + 资源有限 + 目标最优”的问题，都可以尝试树形DP建模。

AI 应用场景

Python 演示

# 树的最大独立集（树形DP + 后序遍历）import sys sys.setrecursionlimit(10 ** 6) def solve(n, edges, weights):    children = [[] for _ in range(n)]    for u, v in edges:        children[u].append(v)        children[v].append(u)     dp = [[0, 0] for _ in range(n)]  # dp[u][0] 不选 u, dp[u][1] 选 u     def dfs(u, parent):        dp[u][1] = weights[u]        for v in children[u]:            if v == parent:                continue            dfs(v, u)            dp[u][1] += dp[v][0]              # 选了 u, 孩子只能不选            dp[u][0] += max(dp[v][0], dp[v][1])  # 不选 u, 孩子自由选择     dfs(0, -1)    return max(dp[0][0], dp[0][1]) if __name__ == "__main__":    # 测试: 6 个节点的树, 每个节点的权值    n = 6    edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)]    weights = [5, 3, 4, 2, 6, 1]    ans = solve(n, edges, weights)    print("最大独立集权值和:", ans)    # 期望: 选 0, 3, 4, 5? 验证: 0 与 1 相邻不能同选, 0 与 2 相邻不能同选    # 正确解: 选 0(5) + 3(2) + 4(6) + 5(1) = 14

1. dp = [[0, 0] for _ in range(n)]每个节点开两个状态位，0 表示不选该节点，1 表示选该节点。
2. def dfs(u, parent):用 parent 参数记住来路，避免在无向树中走回父节点形成死循环。
3. for v in children[u]:遍历所有邻居，但 if v == parent: continue 跳过“来时的路”，剩下全是真孩子。
4. dfs(v, u)先递归孩子，这是后序遍历的关键：等孩子的 dp 算好再处理当前节点。
5. dp[u][1] += dp[v][0]选了 u，相邻的孩子 v 只能不选，所以累加“孩子不选”状态。
6. dp[u][0] += max(dp[v][0], dp[v][1])不选 u，孩子可以自由选或弃，取两者较大值。

常见误区

面试题