C++ 树形动态规划：从原理到实战深度解析

步骤 3：递归遍历（DFS）

以根节点为起点，递归遍历每个节点的所有子节点：

1. 遍历邻接节点 v；
2. 若 v 是父节点则跳过；
3. 递归调用 dfs(v, u)；
4. 回溯时合并子节点 v 的状态到父节点 u。

步骤 4：状态合并（核心）

根据转移逻辑合并状态。例如：

• 若 u 选，则 v 不能选：dp[u][1] += dp[v][0]；
• 若 u 不选，则 v 可选可不选：dp[u][0] += max(dp[v][0], dp[v][1])。

通用模板

// 递归处理节点 u，fa 是 u 的父节点
void dfs(int u, int fa) {
    // 初始化当前节点的状态
    init_dp(u);
    
    // 遍历所有邻接节点
    for (auto v : adj[u]) {
        if (v == fa) continue; // 跳过父节点
        
        dfs(v, u);             // 递归处理子节点
        merge_dp(u, v);        // 状态合并
    }
}

int main() {
    int n;
    cin >> n;
    // 输入 n-1 条边，构建邻接表
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }
    
    dfs(1, -1); // 以 1 为根，父节点为 -1
    cout << get_ans() << endl;
    return 0;
}

三、入门例题 1：树的最大独立集

解题思路

1. 状态定义：
   • dp[u][0]：不选节点 u 时，u 的子树能得到的最大权值和。
   • dp[u][1]：选节点 u 时，u 的子树能得到的最大权值和。
2. 初始化：
   • dp[u][1] = w[u]（选 u，初始权值为自身）。
   • dp[u][0] = 0（不选 u，初始权值为 0）。
3. 状态转移：
   • 选 u：所有子节点 v 都不能选，dp[u][1] += dp[v][0]。
   • 不选 u：子节点 v 可选可不选，取最大值，dp[u][0] += max(dp[v][0], dp[v][1])。
4. 最终答案：max(dp[root][0], dp[root][1])。

完整代码实现

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

using namespace std;

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN];
int w[MAXN];
long long dp[MAXN][2]; // dp[u][0] 不选 u，dp[u][1] 选 u

void dfs(int u, int fa) {
    // 初始化状态
    dp[u][1] = w[u];
    dp[u][0] = 0;

    // 遍历所有子节点
    for (auto v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u); // 先处理子节点

        // 状态转移：合并子节点的结果
        dp[u][1] += dp[v][0];                  // 选 u，子节点必须不选
        dp[u][0] += max(dp[v][0], dp[v][1]);   // 不选 u，子节点选或不选取最大
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    // 输入节点权值
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
    }
    
    // 输入 n-1 条边，构建邻接表
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // 以 1 为根节点，父节点为 -1
    dfs(1, -1);
    
    // 输出最大独立集的权值和
    cout << max(dp[1][0], dp[1][1]) << endl;
    return 0;
}

代码核心解析

• 邻接表存储：无向边双向存储，遍历时通过父节点过滤回退路径。
• 递归逻辑：先递归处理所有子节点，再回溯合并状态，这是'自底向上'的核心。
• 数据类型：使用 long long 避免权值和过大导致的溢出。

你可能会问，为什么必须先处理子节点？因为树形 DP 的本质是'子树的解推导父节点的解'，如果顺序反了，子节点状态未计算，父节点就无法正确合并。

四、入门例题 2：树的直径

树的直径是指树上任意两个节点之间的最长简单路径。除了两次 DFS/BFS 方法外，树形 DP 同样适用，且更适合处理带权或受限场景。

解题思路

1. 状态定义：
   • dp[u]：从节点 u 出发，向下走到其子树中的最长路径长度。
2. 状态转移：
   • 对于子节点 v，边权为 w，则 dp[u] = max(dp[u], dp[v] + w)。
   • 同时维护 u 的'最长路径'和'次长路径'，两者之和即为以 u 为拐点的最长路径。
3. 最终答案：遍历所有节点的'最长路径 + 次长路径'，取最大值。

完整代码实现

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

using namespace std;

const int MAXN = 1e5 + 5;
vector<pair<int, int>> adj[MAXN]; // pair<子节点 v，边权 w>
long long dp[MAXN];               // dp[u]：u 到子树的最长路径
long long ans;                    // 存储树的直径

void dfs(int u, int fa) {
    dp[u] = 0;
    long long max1 = 0, max2 = 0; // 最长、次长路径

    for (auto& edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;
        if (v == fa) continue;

        dfs(v, u);

        // 计算 u 到 v 子树的路径长度
        long long cur = dp[v] + w;

        // 更新最长、次长路径
        if (cur > max1) {
            max2 = max1;
            max1 = cur;
        } else if (cur > max2) {
            max2 = cur;
        }

        dp[u] = max(dp[u], cur);
    }

    // 以 u 为拐点的最长路径 = 最长 + 次长
    ans = max(ans, max1 + max2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    // 输入 n-1 条边（u, v, w）
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    
    ans = 0;
    dfs(1, -1);
    
    cout << "树的直径：" << ans << endl;
    return 0;
}

核心区别与解析

• 状态简化：状态是一维的，但需额外维护'最长'和'次长'路径。
• 答案更新时机：答案不是根节点的状态，而是遍历过程中的最大值，因为直径可能出现在任意子树的拐点。
• 适用性：相比两次 DFS，树形 DP 更能灵活处理点权、带限制的场景。

五、进阶例题 1：树上背包

树上背包是'树形 DP + 分组背包'的结合体。核心在于每个节点的子树对应一组物品，选择子树中的节点相当于选择该组的物品。

问题定义

给定一棵树，每个节点有权值，选择恰好 m 个节点，且选中的节点构成连通块，求最大权值和。

解题思路

1. 状态定义：
   • dp[u][k]：在节点 u 的子树中，选择恰好 k 个节点（包含 u），且构成连通块的最大权值和。
2. 初始化：
   • dp[u][1] = w[u]；其余为 -INF。
3. 状态转移：
   • 类似分组背包，对每个子节点 v，枚举 k 从大到小，避免重复选择。
   • dp[u][k] = max(dp[u][k], dp[u][x] + dp[v][y])。

完整代码实现

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

using namespace std;

const int MAXN = 105;
const int INF = INT_MAX / 2;

vector<int> adj[MAXN];
int w[MAXN];
int dp[MAXN][MAXN]; // dp[u][k]：u 子树选 k 个节点（含 u）的最大权值和
int size_[MAXN];    // size_[u]：u 子树的节点数

void dfs(int u, int fa) {
    size_[u] = 1;
    dp[u][1] = w[u];

    for (auto v : adj[u]) {
        if (v == fa) continue;
        
        dfs(v, u);
        size_[u] += size_[v];

        // 分组背包：k 从大到小枚举，避免重复选
        for (int k = size_[u]; k >= 1; --k) {
            for (int x = min(k - 1, size_[u] - size_[v]); x >= 1; --x) {
                int y = k - x;
                if (y < 0 || y > size_[v]) continue;
                if (dp[u][x] == -INF || dp[v][y] == -INF) continue;
                
                dp[u][k] = max(dp[u][k], dp[u][x] + dp[v][y]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    // 初始化 dp 为负无穷
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dp[i][j] = -INF;
        }
    }
    
    // 输入节点权值
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
    }
    
    // 输入边
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    dfs(1, -1);
    
    cout << (dp[1][m] == -INF ? -1 : dp[1][m]) << endl;
    return 0;
}

核心难点解析

• 分组背包逻辑：每个子节点对应一组选项，父节点 k 从大到小枚举防止重复。
• 状态初始化：用 -INF 表示不可行，只有合法状态才会被更新。
• 复杂度：O(n²)，适用于 n≤100 的场景。

六、进阶例题 2：换根法（二次扫描）

当需要求'每个节点作为根时的最优解'时，可以使用换根 DP。核心是先做一次 DFS 计算子树状态，再做一次 DFS 将根的状态转移到子节点。

问题定义

给定一棵树，求每个节点 u 到其他所有节点的距离之和。

解题思路

第一步：第一次 DFS（自底向上）

1. 状态定义：
   • dp[u]：以 u 为根的子树中，所有子节点到 u 的距离之和。
   • size_[u]：以 u 为根的子树的节点数。
2. 状态转移：
   • size_[u] = 1 + sum(size_[v])。
   • dp[u] = sum(dp[v] + size_[v])。

第二步：第二次 DFS（自顶向下，换根）

1. 状态转移：
   • 假设当前根是 u，换成子节点 v：
   • ans[v] = ans[u] - size_[v] + (n - size_[v])。
   • 解释：v 的子树内节点距离减 1，子树外节点距离加 1。

完整代码实现

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN];
long long dp[MAXN];      // 子树内距离和
long long ans[MAXN];     // 每个节点的总距离和
int size_[MAXN];         // 子树节点数
int n;

// 第一次 DFS：自底向上计算 dp 和 size_
void dfs1(int u, int fa) {
    size_[u] = 1;
    dp[u] = 0;
    
    for (auto v : adj[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        size_[u] += size_[v];
        dp[u] += dp[v] + size_[v];
    }
}

// 第二次 DFS：自顶向下换根计算 ans
void dfs2(int u, int fa) {
    for (auto v : adj[u]) {
        if (v == fa) continue;
        
        // 换根：u→v
        ans[v] = ans[u] - size_[v] + (n - size_[v]);
        dfs2(v, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // 第一次 DFS：以 1 为根
    dfs1(1, -1);
    ans[1] = dp[1];
    
    // 第二次 DFS：换根
    dfs2(1, -1);
    
    // 输出每个节点的距离和
    for (int i = 1; i <= n; ++i) {
        cout << "节点" << i << "的距离和：" << ans[i] << endl;
    }
    
    return 0;
}

核心解析

• 两次 DFS 的意义：第一次算子树内状态，第二次利用父节点推导子节点。
• 换根转移方程：核心是距离的增减变化。
• 复杂度：O(n)，适合大规模数据。

七、常见坑点与优化

新手容易踩的几个坑：

1. 父节点过滤错误：未跳过父节点导致死循环。
2. 状态初始化错误：如未初始化负无穷或自身权值。
3. 枚举顺序错误：树上背包 k 未从大到小枚举。
4. 数据溢出：未用 long long 存储距离和。
5. 换根逻辑错误：未正确计算子树大小和距离增减。

通用优化技巧

• 邻接表优化：预分配空间，减少动态扩容开销。
• 状态压缩：二维状态可拆分为多个一维数组。
• 剪枝优化：跳过无效状态（如 -INF）。

八、经典应用场景

• 最优解类：最小支配集、最小点覆盖、树上最长链。
• 计数类：独立集计数、合法路径计数。
• 依赖类：有依赖的背包问题、树上分组问题。

九、总结

树形 DP 的核心在于理解树的递归结构，并灵活设计状态转移。建议先吃透最大独立集和树的直径，再练习树上背包和换根法。记住，框架是固定的，但状态转移需要根据问题调整。只要想清楚'父节点的状态如何由子节点的状态推导'，就能设计出正确的方程。

从简单例题入手，逐步攻克复杂场景，你会发现树形 DP 其实并不难。