什么是树形 DP
树形动态规划是把动态规划思想应用到树结构上：利用树的层次与递归结构，把”整棵树的最优解”分解为”子树的最优解”逐层合并。它几乎总是通过 DFS 实现，复杂度一般为 O(n)。
树形 DP 的三个特征：
- 层次性：树天然分层，适合自底向上（先子后父）或自顶向下（先父后子）递推；
- 递归性：子树是独立子问题，可以递归求解后合并；
- 无后效性：父节点状态只依赖子节点状态，满足 DP 的无后效性要求。
两种遍历方向
叶 → 根（后序遍历）
先递归处理子节点，再用子节点信息更新父节点——树形 DP 的主流形式：
void dfs(int u, int parent) {
for (int v : tree[u]) {
if (v == parent) continue;
dfs(v, u); // 先算子树
// 用 dp[v] 更新 dp[u]
}
}
根 → 叶（先序遍历）
先处理父节点，再把信息向下传递给子节点，常用于”换根 DP”等需要父亲影响儿子的场景：
void dfs(int u, int parent) {
// 用父节点传来的信息初始化 dp[u]
for (int v : tree[u]) {
if (v == parent) continue;
dfs(v, u); // 把信息传给子节点
}
}
经典问题
1. 没有上司的舞会（最大独立集）
选择若干节点，要求不能同时选相邻节点，求选中节点价值和最大。
状态：dp[u][0] 不选 u 的最大值；dp[u][1] 选 u 的最大值。转移：
void dfs(int u, int parent) {
dp[u][1] = value[u]; // 选 u
for (int v : tree[u]) {
if (v == parent) continue;
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]); // u 不选：子节点随便
dp[u][1] += dp[v][0]; // u 选了：子节点必须不选
}
}
2. 树的直径
求树上任意两点间的最长路径。对每个节点记录 d1[u]（向下的最长链）和 d2[u]（次长链），答案就是全局最大的 d1[u] + d2[u]：
void dfs(int u, int parent) {
for (auto [v, w] : tree[u]) {
if (v == parent) continue;
dfs(v, u);
int len = d1[v] + w;
if (len > d1[u]) { d2[u] = d1[u]; d1[u] = len; }
else if (len > d2[u]) { d2[u] = len; }
}
diameter = max(diameter, d1[u] + d2[u]);
}
3. 树上背包（选课问题）
课程有依赖关系（先修课），选 m 门课使总学分最大。设 dp[u][j] 为以 u 为根的子树中选 j 门课的最大值，用子树做”分组背包”合并，容量倒序保证每棵子树最多贡献一次：
void dfs(int u) {
dp[u][1] = credit[u]; // 先修课本身占一门
for (int v : tree[u]) {
dfs(v);
for (int j = m; j >= 1; j--) // 容量倒序
for (int k = 1; k < j; k++)
dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
}
}
解题套路
- 状态设计：一般用
dp[u][k]表示”以 u 为根的子树 + 附加状态 k”的最优解；附加状态常用来表达父子约束（选了没有、颜色、是否在子树内等）； - 存储：用邻接表或链式前向星，注意传入父节点防止回访；
- 森林处理：多棵树时加一个虚拟根节点统一 DFS；
- 换根 DP：先算出以 1 为根的答案，再通过”父子树贡献回传”在第二次 DFS 中求出所有节点为根时的答案，是树上题的高频进阶技巧。
常见变种
树的重心、树的最小点/边覆盖、树的匹配、树上的最大权独立集（去掉相邻限制的变体）等，核心都是”定好状态、子树合并”。