🌳 什么是树形 DP？

定义与概念

树形动态规划（Tree DP）是一种在树形结构上进行动态规划的算法。它通常通过递归的方式，从叶节点向上（或从根节点向下再向上汇总）计算状态，最终得到整个树的某个最优解。

核心思想是将原问题分解为与各个子树相关的子问题，然后合并子问题的解来得到当前节点（子树）的解。

核心思想： 将复杂的树形问题分解为子树问题，通过状态转移方程合并子问题的解。通常使用深度优先搜索（DFS）遍历树，在回溯时进行状态计算和合并。

适用场景

求解以某个节点为根的子树相关的最优值问题（例如：子树的最大权值和、子树的某种特性计数）。
树上的路径优化问题（例如：树的直径）。
树上的选择/分配问题（例如：最大独立集、树上背包）。
树的结构统计问题（例如：特定结构的子树数量）。

状态表示

状态的定义是树形 DP 的关键。通常，状态会与节点相关联，例如：dp[u] 表示以节点 u 为根的子树，在满足某些条件下的最优解或方案数。有时状态可能需要多个维度，如 dp[u][state_type]，其中 state_type 表示节点 u 的不同状态（例如：是否选择节点 u）。

1

2

4

5

3

点击节点以高亮。树形DP通常从叶节点开始，向上计算到根节点。

dp[u] = f(dp[v₁], dp[v₂], ..., dp[v_k], u的属性)
其中 v₁, v₂, ..., v_k 是 u 的所有子节点

这里的函数 f 代表状态转移方程，它描述了如何根据子节点的状态和节点 u 本身的属性（如权值）来计算节点 u 的状态。

🔄 树形 DP 的核心转移方式

通用套路：深度优先搜索 (DFS)

树形 DP 通常依赖于 DFS 遍历。在 DFS过程中，我们先递归处理当前节点的所有子树，当子树的结果计算完毕后（即 DFS 从子节点返回时），再利用这些子树的结果来计算当前节点的状态。

// 树形 DP 基本框架 (C++)
// adj 是邻接表, dp数组存储状态, value可能存储节点权值等
// parent 参数用于防止 DFS 时走回头路到父节点

void dfs(int u, int p) {
    // 1. 初始化 dp[u] 的某些基础状态
    //    例如，如果 dp[u] 包含节点u自身的贡献，可以在这里加上
    //    dp[u][state_if_u_is_chosen] = value[u];
    //    dp[u][state_if_u_is_not_chosen] = 0;

    // 2. 遍历 u 的所有子节点 v
    for (int v : adj[u]) {
        if (v == p) continue; // 避免访问父节点

        dfs(v, u); // 递归处理子树 v

        // 3. 状态合并：根据子节点 v 的 dp 状态更新父节点 u 的 dp 状态
        //    这是树形 DP 的核心步骤
        //    例如: dp[u] = combine(dp[u], dp[v]);
        //    具体合并方式取决于问题定义
        //    dp[u][state_A] += dp[v][state_X];
        //    dp[u][state_B] = max(dp[u][state_B], dp[v][state_Y] + cost(u,v));
    }

    // 4. (可选) 完成所有子节点的合并后，对 dp[u] 进行最终处理
    //    例如，如果 dp[u] 需要考虑 u 本身的某种属性，但这个属性依赖于所有子树处理完毕
    //    update_final_dp_for_u(dp[u]);
}

状态合并的常见方式

求和型： dp[u] += dp[v] (例如，统计子树的某种总数)
取最值型： dp[u] = max(dp[u], dp[v] + cost(u,v)) (例如，求最长路径或最大权值)
组合选择型： dp[u][state1] += dp[v][stateA] * dp[v][stateB] (例如，计数问题中的组合)
条件依赖型： 常见于最大独立集、树上背包等，父节点的状态会影响子节点能选择的状态。
dp[u][选] = value[u] + Σ dp[v][不选]
dp[u][不选] = Σ max(dp[v][选], dp[v][不选])

节点 4 (叶)
dp[4] = 3

节点 2
dp[2] from dp[4]?

节点 3 (叶)
dp[3] = 8

节点 1 (根)
dp[1] from dp[2], dp[3]?

假设一个简单的求子树权值和的例子：dp[u] = value[u] + Σ dp[v]。叶节点的dp值是其自身权值。计算顺序：dp[4] → dp[2] (结合value[2]) → dp[3] → dp[1] (结合value[1])。

注意事项：

避免重复访问： 在 DFS 中传递父节点 p，跳过 v == p 的情况。
正确的递归顺序： 必须先完成对所有子节点 v 的 dfs(v, u) 调用，才能用 dp[v] 更新 dp[u]。
状态初始化： dp 数组的初始值非常重要。对于求和，通常初始化为0；对于求最大值，初始化为负无穷；对于求最小值，初始化为正无穷。
根节点的选择： 如果题目未指定根，可以任选一个节点（如节点1）开始DFS。对于某些问题（如换根DP），则需要特殊处理。

📝 典型例题：树上最大独立集

问题描述

给定一棵包含 N 个节点的树，每个节点都有一个权值。你需要在这棵树上选择一个节点的集合，使得集合中任意两个节点之间没有边直接相连（即它们不是父子或兄弟关系，只要有边就不行）。目标是最大化选中节点的总权值。

这个集合被称为树的**独立集**，我们要求的是**最大权独立集**。

状态设计

对于树上的每个节点 u，我们需要考虑两种情况：

dp[u][0]：以 u 为根的子树中，不选择节点 u 时，能获得的最大权值和。
dp[u][1]：以 u 为根的子树中，选择节点 u 时，能获得的最大权值和。

状态转移方程

设 value[u] 是节点 u 的权值，v 是 u 的一个子节点。

dp[u][0] = Σ_{v ∈ children(u)} max(dp[v][0], dp[v][1])

解释 dp[u][0]： 如果不选择节点 u，那么对于 u 的每个子节点 v，我们既可以选择 v（取 dp[v][1]），也可以不选择 v（取 dp[v][0]）。为了使总权值最大，我们对每个子节点 v 都取其两种状态下的较大值，然后累加起来。

dp[u][1] = value[u] + Σ_{v ∈ children(u)} dp[v][0]

解释 dp[u][1]： 如果选择节点 u，那么根据独立集的定义，它的所有直接子节点 v 都不能被选择。因此，对于每个子节点 v，我们只能取 dp[v][0]（即不选择 v 时的最大权值）。value[u] 是选择节点 u 本身获得的权值。

最终答案： 对于根节点 root（例如，节点1），最终答案是 max(dp[root][0], dp[root][1])。

完整代码实现 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005; // 最大节点数
vector<int> adj[MAXN];   // 邻接表存储树
int value[MAXN];         // 节点权值
long long dp[MAXN][2];   // dp[u][0]: u不选, dp[u][1]: u选 (使用long long防止权值和溢出)

// u: 当前节点, p: u的父节点
void dfs(int u, int p) {
    // 初始化当前节点的状态
    dp[u][0] = 0;           // 不选u，则初始贡献为0
    dp[u][1] = value[u];    // 选u，则初始贡献为u的权值

    for (int v : adj[u]) {
        if (v == p) continue; // 跳过父节点

        dfs(v, u); // 递归处理子树

        // 状态转移
        // 如果不选 u (dp[u][0])，则子节点 v 可以选也可以不选，取两者最大值
        dp[u][0] += max(dp[v][0], dp[v][1]);
        
        // 如果选 u (dp[u][1])，则子节点 v 必须不选
        dp[u][1] += dp[v][0];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 读入节点权值 (假设节点编号从1到n)
    for (int i = 1; i <= n; i++) {
        cin >> value[i];
    }

    // 读入树的边 (n-1条边)
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    
    // 从节点1开始DFS (假设1是根节点，或者任选一个节点开始)
    dfs(1, 0); // 0可以表示一个不存在的父节点

    // 最终答案是根节点选与不选两种情况的最大值
    cout << max(dp[1][0], dp[1][1]) << endl;

    return 0;
}

时间复杂度： O(N)，因为每个节点和每条边在 DFS 中只被访问常数次。
空间复杂度： O(N)，用于存储邻接表、节点权值和 DP 状态数组。如果树的深度过大，递归栈也可能达到 O(N)。

📚 常见树形 DP 模板与问题类型

树形 DP 的应用非常广泛，以下是一些经典的问题类型及其核心思想：

1. 树的直径（最长链）

问题： 求树上任意两点间路径长度的最大值。

思路： 对每个节点 u，维护以 u 为根的子树中，从 u 出发向下的最长链 d1[u] 和次长链 d2[u]（要求这两条链不经过同一个子节点）。经过 u 的最长链长度即为 d1[u] + d2[u]。树的直径就是所有节点 u 的 d1[u] + d2[u] 的最大值。也可以通过两次DFS求解。

2. 树上背包

问题： 每个节点代表一个物品，有体积和价值。选择一个节点必须先选择其父节点（或者无此限制，但仍是树形依赖）。在总体积不超过背包容量的前提下，求最大总价值。

思路： dp[u][j] 表示以 u 为根的子树中，分配容量 j 能获得的最大价值。合并子节点 v 的信息到 u 时，类似于分组背包：对 u 的每个子节点 v，枚举分配给子树 v 的容量 k，然后更新 dp[u][j]。

3. 树上染色/计数问题

问题： 给树的节点染色，满足某些约束（如相邻节点颜色不同），求方案数或最优染色代价。

思路： dp[u][color] 表示以 u 为根的子树中，节点 u 染成 color 时的方案数或最小代价。转移时考虑子节点 v 的颜色不能与 u 的颜色冲突。

4. 换根 DP (Re-rooting)

问题： 求解对于树中每一个节点，当它作为根时，整个树的某个属性值（例如，到其他所有节点距离之和最小，或最远点距离）。

思路： 通常需要两次 DFS。第一次 DFS（自底向上）计算每个节点子树内的信息（例如，子树大小，子树内所有节点到该节点的距离和）。第二次 DFS（自顶向下）利用父节点已经计算好的全局信息和子树信息，来推导出当前节点作为整棵树的根时的答案。

学习建议：

掌握基础框架： 深刻理解 DFS 如何驱动状态计算和合并。
状态定义是关键： 仔细思考需要哪些信息来唯一确定子问题的解，并能有效地转移到父问题。
多练习： 不同类型的题目有其独特的转移方式，通过练习积累经验。
边界条件： 叶节点如何初始化？空子树如何处理？
画图分析： 对于复杂问题，画出小规模的树和 DP过程有助于理解。

树形 DP vs 普通（线性/区间）DP

普通 DP
通常处理线性序列、网格或区间等规则结构。
状态转移方向明确（如从左到右，从小区间到大区间）。

树形 DP
处理树或森林等非线性结构。
状态转移依赖于树的父子关系，通常通过 DFS 在递归回溯时进行。

🧠 练习与自我检测

选择题练习

1. 树形 DP 的状态计算通常依赖于哪种遍历方式完成子问题的求解？

A. 广度优先搜索（BFS）

B. 深度优先搜索（DFS）

C. 拓扑排序

D. Dijkstra 算法

2. 在树上最大独立集问题中，如果选择当前节点 `u` (`dp[u][1]`)，其子节点 `v` 的状态应如何考虑？

A. 子节点 v 也可以选择 (dp[v][1])

B. 子节点 v 必须不选择 (dp[v][0])

C. 子节点 v 可选可不选，取较大值 (max(dp[v][0], dp[v][1]))

D. 与子节点状态无关

3. 树形 DP 中“状态合并”——即父节点状态由子节点状态计算得出——主要在 DFS 过程的哪个阶段发生？

A. 访问到当前节点，即将递归其子节点之前

B. 从所有子节点的递归调用返回之后，当前节点即将返回给其父节点之前

C. DFS 开始之前，进行全局初始化时

D. 整个 DFS 结束后，统一处理所有 DP 值时

4. 下列哪个问题通常不直接适用朴素的树形 DP 思想（可能需要更复杂的图算法）？

A. 树的直径

B. 树上带依赖的背包问题

C. 任意图中两点间的最短路径

D. 统计树中每个子树的节点个数

5. 在一个典型的树形 DP 的 DFS 函数 `void dfs(int u, int p)` 中，`dp[u]` 的值主要依赖于：

A. 节点 u 的父节点 p 的 dp 值

B. 节点 u 的所有子节点 v 的 dp 值

C. 与 u 同深度的其他节点的 dp 值

D. 树的根节点的 dp 值

💻 编程练习

练习题 1：树上最大独立集

题目描述： 你已经学习了树上最大独立集的原理。现在请你实现它。给定一棵有 N 个节点的树，每个节点有一个权值。选择一些节点，使得任意两个相邻的节点（即有边直接连接的节点）不能同时被选择，求选中节点的最大权值和。

输入格式：

第一行：一个整数 N (1 ≤ N ≤ 1000)，表示节点数。节点编号为 1 到 N。
第二行：N 个整数，w₁, w₂, ..., w_N，表示每个节点的权值 (1 ≤ w_i ≤ 1000)。
接下来 N-1 行：每行两个整数 u, v (1 ≤ u, v ≤ N, u ≠ v)，表示节点 u 和 v 之间有一条边。

输出格式：

一个整数，表示最大权值和。

测试输入样例：

测试输出样例：

练习题 2：树上背包（简化版：依赖父节点）

题目描述： 你有一棵有 N 个节点的树，每个节点 i 代表一件物品，它有体积 c_i 和价值 w_i。你还有一个容量为 V 的背包。选择物品时有一个限制：如果要选择节点 i，那么必须先选择它的父节点（根节点没有父节点，可以直接选择）。请问在不超过背包总容量 V 的前提下，能获得的最大总价值是多少？（假设树以节点1为根）