什么是树形 DP？

树形 DP（Dynamic Programming on Trees）是一种在 树结构 上使用 动态规划 解决问题的方法。它的核心思想是 自底向上 递归计算，每个节点的状态依赖于它的子节点的计算结果。

如果你熟悉普通的 动态规划（DP），你可以把树形 DP 理解为：

• 普通 DP 在一维或二维数组上进行（如最长子序列、背包问题）。
• 树形 DP 在树的节点之间进行（如子树计算、路径问题）。

---

树形 DP 的应用场景

树形 DP 主要用于 涉及树结构的最优决策问题，常见的题目类型包括：

1. 树的最小覆盖问题

题目： 选最少的节点，使得树中的所有边至少有一个端点被选。 解法： 定义 dp[u][0] 表示 u 不选，dp[u][1] 表示 u 选，递归计算。

2. 树的最大权路径和

题目： 给定一棵树，每条边上有权重，求从某个节点出发的最长路径。 解法： dp[u] 代表以 u 为根的子树的最长路径，递归求解。

3. 树的直径（最长路径）

题目： 求一棵树中两点之间的最长路径。 解法： 两次 DFS 或树形 DP 计算最长路径。

4. 树的最小删除代价

题目： 删除最少的节点，使得树变成某种结构（如二叉树）。 解法： dp[u] 表示删掉 u 的最小代价。

5. 祖先/子孙信息计算

题目： 计算树上每个节点的子孙数量、深度等信息。 解法： dp[u] 递归计算 u 的子树大小。

---

树形 DP 的基本步骤

1. 建树（用邻接表存储）。
2. 定义 DP 状态（每个节点可能有多种状态，如放置与不放置士兵）。
3. 递归计算 DP（从叶子节点开始往上计算）。
4. 返回根节点的最优解（一般是 min(dp[root][0], dp[root][1])）。

---

总结

树形 DP 是在树上进行的动态规划，通常用于计算子树信息、自底向上的最优决策，在树的路径问题、覆盖问题、删除问题、优化问题等场景中非常常见。它的核心是 递归计算每个节点的状态，并将结果传递给父节点。