树形动态规划（Tree DP）是一种在树结构上进行动态规划的算法，常用于解决与树相关的最优化问题。其核心思想是利用递归和子问题分解，通过子树的结果推导出当前节点的结果。

核心思想

  1. 树结构：树是一种无向无环图，具有层次性，通常以根节点为起点。
  2. 动态规划：通过子问题的解推导当前问题的解，避免重复计算。

基本步骤

  1. 状态定义：为每个节点定义状态，表示以该节点为根的子树的性质。
  2. 状态转移：根据子节点的状态推导当前节点的状态。
  3. 递归求解：从叶子节点开始，递归计算每个节点的状态。
  4. 结果获取：最终结果通常存储在根节点或通过遍历所有节点得到。

常见问题

  1. 最大独立集：选择不相邻的节点，使权重和最大。
  2. 最小点覆盖：选择最少的节点覆盖所有边。
  3. 最长路径：找到树中最长的路径。

示例：最大独立集

  • 状态定义：dp[u][0]表示不选节点u时的最大权重，dp[u][1]表示选择节点u时的最大权重。
  • 状态转移：
    • 不选u：dp[u][0] = sum(max(dp[v][0], dp[v][1]))，v为u的子节点。
    • 选u：dp[u][1] = weight[u] + sum(dp[v][0])。
  • 递归求解：从叶子节点开始计算。
  • 结果获取：max(dp[root][0], dp[root][1])。

代码框架（伪代码）

1
2
3
4
5
6
7
8
9
10
11
12
def tree_dp(u, parent):
    dp[u][0] = 0  # 不选u
    dp[u][1] = weight[u]  # 选u
    for v in children[u]:
        if v != parent:
            tree_dp(v, u)
            dp[u][0] += max(dp[v][0], dp[v][1])
            dp[u][1] += dp[v][0]

# 调用
tree_dp(root, -1)
result = max(dp[root][0], dp[root][1])

总结

树形DP通过递归和子问题分解，利用树的结构特性，高效解决树上的最优化问题。关键在于合理定义状态和转移方程。