Part 5.5：树形 DP

引言：公司派对的最大欢乐值

想象一下，你是一家公司的 HR，正在组织一场盛大的公司派对。为了让派对气氛尽可能活跃，你希望邀请尽可能多的员工参加。但是，有一个尴尬的规定：如果一个员工参加了派对，那么他的直接上司就不能参加（因为上司在场，下属放不开）。

公司的组织架构是一棵树（CEO 是根节点），每个员工都有一个“欢乐指数”。你的任务是：制定一份邀请名单，使得参加派对的所有员工的欢乐指数之和最大，同时满足上述规定。

这个问题，就是经典的树形动态规划 (Tree DP) 入门问题——“没有上司的舞会”，在学术上也被称为树的最大权独立集 (Maximum Weight Independent Set on a Tree) 问题。

为什么树形 DP 如此重要？

面试价值：树形 DP 是 DP 与树形结构相结合的产物，是考察候选人对递归、DFS 和 DP 思想综合运用能力的利器。能解决树形 DP 问题，意味着你对非线性结构的动态规划有了深刻理解。
工程价值：树形 DP 的思想可以应用于任何具有树状依赖关系的最优化问题。例如，在计算机网络中，选择最优的路由节点；在文件系统中，计算目录树的某种最优属性；在社交网络中，分析影响力传播等。

与线性 DP 和区间 DP 不同，树形 DP 没有固定的“从左到右”或“由小到大”的迭代顺序。它的迭代依赖于树的结构，通常通过深度优先搜索 (DFS) 来实现状态的自底向上转移。

本文将以“没有上司的舞会”为例，带你深入理解树形 DP 的思考方式和实现范式。

背景知识：树的遍历与后序思想

要理解树形 DP，你必须对树的深度优先搜索 (DFS)，特别是后序遍历 (Post-order Traversal) 有深刻的理解。

后序遍历：其访问顺序是“左子树 → 右子树 → 根节点”。

这个顺序的精髓在于：在处理任何一个节点之前，我们已经处理完了它的所有子节点（子树）。

这与树形 DP 的思想完美契合！树形 DP 的核心就是：一个节点 u 的最优解，可以通过其所有子节点 v 的最优解来推导。后序遍历天然地为我们提供了这种“自底向上”计算状态的顺序。

因此，几乎所有的树形 DP 问题，其代码实现框架都是一个 DFS（后序遍历）。

详细算法原理

1. 算法的“直觉”：每个员工的两种选择

对于公司里的每一个员工（节点 u），我们来分析他的状态。在制定邀请名单时，他只有两种可能性：

u 参加派对：如果 u 参加，那么他的所有直接下属（子节点 v）都不能参加。此时，以 u 为根的这个“部门”能贡献的最大欢乐值，就是 u 自己的欢乐指数，加上他所有孙子辈及以下部门的最大欢乐值（因为下属不能参加，所以要考虑下属的下属）。
u 不参加派对：如果 u 不参加，那么他的直接下属（子节点 v）就获得了自由，他们可以参加，也可以不参加。为了让总欢乐值最大，我们应该让每个下属 v 所在的“子部门”都贡献出他们可能的最大欢乐值（无论 v 自己是否参加）。此时，以 u 为根的这个“部门”能贡献的最大欢乐值，就是他所有下属部门最大欢乐值的总和。

一个节点的最终决策，取决于这两种可能性中，哪一种能带来的总欢乐值更大。

2. 严谨原理：状态定义与状态转移方程

根据上面的直觉，我们可以为每个节点 u 定义两个状态：

dp[u][1]：表示在以 u 为根的子树中，邀请 u 参加派对所能获得的最大欢乐指数之和。
dp[u][0]：表示在以 u 为根的_子树中，不邀请 u 参加派对所能获得的最大欢乐指数之和。

状态转移方程

我们通过对节点 u 进行 DFS（后序遍历）来计算 dp[u][0] 和 dp[u][1]。假设我们已经递归地计算出了 u 的所有子节点 v 的 dp[v][0] 和 dp[v][1] 值。

计算 dp[u][1] (邀请 u)
如果邀请 u，那么 u 的所有直接子节点 v 都不能参加。所以，我们只能从每个子树 v 中获取“不邀请 v”所能带来的最大欢乐值，即 dp[v][0]。
因此，状态转移方程为：
dp[u][1] = happiness[u] + Σ dp[v][0] (对于所有 u 的子节点 v)
计算 dp[u][0] (不邀请 u)
如果不邀请 u，那么 u 的每个子节点 v 都可以自由选择参加或不参加。为了使总欢乐值最大，我们应该为每个子树 v 选择其最优策略，即 max(dp[v][0], dp[v][1])。
因此，状态转移方程为：
dp[u][0] = Σ max(dp[v][0], dp[v][1]) (对于所有 u 的子节点 v)

**初始化 (Base Case)**：
对于叶子节点 leaf：
dp[leaf][1] = happiness[leaf]
dp[leaf][0] = 0
最终结果：
对于树的根节点 root，最终的答案就是 max(dp[root][0], dp[root][1])。

步骤分解 (Step-by-step)

数据结构：使用邻接表来存储树的结构。
创建 DP 表：创建一个 N x 2 的二维数组 dp。
寻找根节点：找到没有父节点的那个节点作为根（或者题目会直接给定）。
**DFS (后序遍历)**：从根节点开始，执行 dfs(root)。
**DFS 函数 dfs(u)**：
a. 初始化：dp[u][1] = happiness[u], dp[u][0] = 0。
b. 递归子节点：遍历 u 的所有子节点 v，递归调用 dfs(v)。
c. 状态转移：在递归返回后，根据子节点 v 的 dp 值来更新 dp[u]：
dp[u][1] += dp[v][0]
dp[u][0] += max(dp[v][0], dp[v][1])
返回结果：dfs(root) 执行完毕后，返回 max(dp[root][0], dp[root][1])。

动画式案例

图示：一个公司组织架构树
节点 (欢乐指数): 0(10), 1(5), 2(8), 3(2), 4(6)
边: (0,1), (0,2), (1,3), (1,4)
根节点: 0

DFS (后序遍历) 过程：

dfs(3): 叶子节点。dp[3][1]=2, dp[3][0]=0。
dfs(4): 叶子节点。dp[4][1]=6, dp[4][0]=0。
dfs(1): 子节点 3, 4 已处理。
- dp[1][1] = h[1] + dp[3][0] + dp[4][0] = 5 + 0 + 0 = 5
- dp[1][0] = max(dp[3][0],dp[3][1]) + max(dp[4][0],dp[4][1]) = max(0,2) + max(0,6) = 2 + 6 = 8
- dp[1] 计算完毕: [8, 5]
dfs(2): 叶子节点。dp[2][1]=8, dp[2][0]=0。
dfs(0): 子节点 1, 2 已处理。
- dp[0][1] = h[0] + dp[1][0] + dp[2][0] = 10 + 8 + 0 = 18
- dp[0][0] = max(dp[1][0],dp[1][1]) + max(dp[2][0],dp[2][1]) = max(8,5) + max(0,8) = 8 + 8 = 16
- dp[0] 计算完毕: [16, 18]

最终结果：max(dp[0][0], dp[0][1]) = max(16, 18) = 18。

Python 实现

def happy_party(happiness, subordinates):
    """
    解决“没有上司的舞会”问题（树的最大权独立集）。
    :param happiness: 每个员工的欢乐指数列表。
    :param subordinates: 邻接表，subordinates[i] 是 i 的直接下属列表。
    :return: 最大欢乐指数之和。
    """
    n = len(happiness)
    if n == 0:
        return 0

    # dp[u][0]: 不邀请 u 的最大欢乐值
    # dp[u][1]: 邀请 u 的最大欢乐值
    dp = [[0, 0] for _ in range(n)]

    def dfs(u):
        # 1. 初始化当前节点
        dp[u][0] = 0
        dp[u][1] = happiness[u]

        # 2. 递归处理所有子节点
        for v in subordinates[u]:
            dfs(v)
            # 3. 根据子节点的结果更新当前节点
            # 如果不邀请 u，则其子节点 v 可来可不来，取最大值
            dp[u][0] += max(dp[v][0], dp[v][1])
            # 如果邀请 u，则其子节点 v 都不能来
            dp[u][1] += dp[v][0]

    # 找到根节点（没有上司的员工）
    has_boss = [False] * n
    for u in range(n):
        for v in subordinates[u]:
            has_boss[v] = True
    
    root = -1
    for i in range(n):
        if not has_boss[i]:
            root = i
            break
    
    if root == -1: # 如果是环状结构（不符合题意），随便选一个起点
        root = 0

    # 从根节点开始 DFS
    dfs(root)

    # 返回最终结果
    return max(dp[root][0], dp[root][1])

# --- 案例测试 ---
happiness = [10, 5, 8, 2, 6]
# 组织架构：0->1, 0->2, 1->3, 1->4
subordinates = [
    [1, 2],  # 0 的下属是 1, 2
    [3, 4],  # 1 的下属是 3, 4
    [],      # 2 是叶子节点
    [],      # 3 是叶子节点
    []       # 4 是叶子节点
]

max_happiness = happy_party(happiness, subordinates)
print(f"派对的最大欢乐指数是: {max_happiness}") # 输出: 18

复杂度推导过程

时间复杂度: O(N)。其中 N 是员工（节点）数量。算法的核心是一个 DFS 遍历，每个节点和每条边都只会被访问一次。
空间复杂度: O(N)。我们需要一个 dp 表来存储 N 个节点的两个状态，空间为 O(N)。同时，DFS 的递归调用栈深度在最坏情况下（链状树）也是 O(N)。

优势 / 劣势 / 易错点

优势

结构清晰：树形 DP 的代码框架通常很固定，就是一次 DFS 遍历。
效率高：线性时间复杂度，非常高效。

劣势

状态定义是关键：如何根据问题定义出合适的状态（例如本题的 dp[u][0] 和 dp[u][1]）是难点。
依赖于树结构：只适用于具有树形结构或可以转化为树形结构的问题。

易错点

找不对根节点：如果图不是从 0 开始的根，需要先找到根节点再进行 DFS。
状态转移混淆：混淆了 dp[u][0] 和 dp[u][1] 的更新逻辑，例如在计算 dp[u][1] 时错误地加了 max(dp[v][0], dp[v][1])。
忘记后序遍历：必须在所有子节点都计算完毕后，才能计算当前节点。DFS 的递归返回天然地保证了这一点。

适用场景

树形 DP 适用于所有需要在树（或森林）上求解最优化问题的场景。

树的最大独立集：本文案例。
树的最小顶点覆盖：选择最少的点覆盖所有的边。
树的最小支配集：选择最少的点，使得所有其他点都与这些点相邻。
树的直径：树上最远两点之间的距离。
背包问题 on Tree：在树的节点上做选择，有背包容量限制。

总结

树形 DP 将动态规划的思想从线性序列扩展到了树形结构。它没有固定的迭代顺序，而是巧妙地利用了深度优先搜索的后序遍历特性，实现了状态的自底向上转移。

本文核心要点

✅ 核心思想：通过 DFS（后序遍历），利用已求得的子树最优解来推导父节点的最优解。
✅ 状态定义：通常需要为每个节点定义多种状态，以应对不同的决策（如本题的“参加”与“不参加”）。
✅ 状态转移：在 DFS 的回溯阶段，根据子节点的状态更新当前节点的状态。
✅ 代码范式：一个 DFS 函数，在递归调用之后执行状态转移计算。
✅ 复杂度：通常是线性时间 O(N) 或 O(N*M)（取决于状态的维度）。

掌握了树形 DP，你就拥有了解决一类复杂结构化数据最优解问题的能力。在下一篇文章中，我们将挑战 DP 中一个更炫酷的分支——状态压缩 DP，学习如何用二进制位来表示和转移状态。

大学算法全体系 > Part 5：动态规划

#算法基础 #动态规划 #DP #树形DP #树的最大独立集

Part 5.5：树形 DP

https://hjjjkh.github.io/posts/d47b8b79

作者

李国强

发布于

2025年11月15日

许可协议

Part 3.1：基础排序算法：冒泡、选择与插入上一篇

Part 2.8：二叉搜索树：有序世界的高效查找下一篇