第 60 课·动态规划高级

树形 DP

tree-dprerootingsubtree

第60课 - 树形 DP

学习目标

  1. 理解树形DP的基本思想：掌握如何将动态规划思想应用到树形结构上
  2. 掌握树形DP的实现模式：学会使用递归（DFS）进行状态转移
  3. 理解子树DP与根节点DP的区别：能够处理从子树到根的DP问题
  4. 学习换根DP（Rerooting）技巧：解决无根树问题的优化方法
  5. 应用树形DP解决经典问题：如树的直径、节点间最大路径和等

核心概念

什么是树形DP？

树形DP是在树结构上进行的动态规划，通常使用深度优先搜索（DFS）来遍历树并计算状态。它的核心思想是：通过递归计算每个子树的信息，然后合并这些信息来得到整棵树的解。

树形DP的基本模式

  1. 自底向上：从叶子节点开始，逐步向根节点传递信息
  2. 状态定义：通常以当前节点为根的子树作为状态
  3. 状态转移：利用子节点的状态来更新当前节点的状态

换根DP（Rerooting）

换根DP是一种优化技巧，用于解决无根树问题。基本思想是：

  • 首先任选一个根节点进行一次树形DP
  • 然后通过"换根"操作，将每个节点依次作为根节点，快速计算出所有节点的答案

代码示例

1. 基础树形DP示例：计算树的直径

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
vector<int> tree[MAXN];
int dp[MAXN];  // dp[i]表示以i为根的子树中，从i出发的最长路径长度
int ans = 0;   // 记录树的直径

void dfs(int node, int parent) {
    dp[node] = 0;
    int max1 = 0, max2 = 0;  // 记录最长和次长的子路径
    
    for (int child : tree[node]) {
        if (child == parent) continue;
        dfs(child, node);
        
        // 更新最长和次长路径
        if (dp[child] + 1 > max1) {
            max2 = max1;
            max1 = dp[child] + 1;
        } else if (dp[child] + 1 > max2) {
            max2 = dp[child] + 1;
        }
    }
    
    // 当前节点的最长路径是经过当前节点的最长路径
    dp[node] = max1;
    // 更新全局直径：经过当前节点的最长路径 = max1 + max2
    ans = max(ans, max1 + max2);
}

int main() {
    int n;
    cin >> n;
    
    // 建树
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    dfs(1, -1);  // 从节点1开始DFS，-1表示没有父节点
    
    cout << "树的直径长度为: " << ans << endl;
    
    return 0;
}

2. 换根DP示例：计算每个节点到其他节点的距离和

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100005;
vector<int> tree[MAXN];
int subtree_size[MAXN];   // 子树大小
long long dist_sum[MAXN]; // 以当前节点为根时，到所有节点的距离和
long long ans[MAXN];      // 最终答案

// 第一次DFS：计算子树大小和以1为根时的距离和
void dfs1(int node, int parent) {
    subtree_size[node] = 1;
    dist_sum[node] = 0;
    
    for (int child : tree[node]) {
        if (child == parent) continue;
        dfs1(child, node);
        subtree_size[node] += subtree_size[child];
        // 子树中每个节点到node的距离比到child的距离多1
        dist_sum[node] += dist_sum[child] + subtree_size[child];
    }
}

// 第二次DFS：换根DP
void dfs2(int node, int parent) {
    ans[node] = dist_sum[node];
    
    for (int child : tree[node]) {
        if (child == parent) continue;
        
        // 保存原始值用于回溯
        long long original_dist_sum = dist_sum[node];
        int original_subtree_size = subtree_size[node];
        
        // 将根从node换到child
        // 1. node的子树大小减少
        subtree_size[node] -= subtree_size[child];
        // 2. node的距离和减少（child子树中的节点现在都近了1）
        dist_sum[node] -= (dist_sum[child] + subtree_size[child]);
        
        // 3. child成为新的根
        subtree_size[child] += subtree_size[node];
        dist_sum[child] += (dist_sum[node] + subtree_size[node]);
        
        // 递归处理child
        dfs2(child, node);
        
        // 回溯：恢复原始值
        dist_sum[node] = original_dist_sum;
        subtree_size[node] = original_subtree_size;
        // child的值在下次循环会重新计算，不需要回溯
    }
}

int main() {
    int n;
    cin >> n;
    
    // 建树
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    // 第一次DFS
    dfs1(1, -1);
    
    // 第二次DFS（换根）
    dfs2(1, -1);
    
    // 输出每个节点的距离和
    for (int i = 1; i <= n; i++) {
        cout << "节点 " << i << " 到其他所有节点的距离和: " << ans[i] << endl;
    }
    
    return 0;
}

实践练习

练习1：基础树形DP - 计算树的最长路径（简单）

题目描述：给定一棵n个节点的树，边有权重。请计算树中最长路径的长度（即树中两点间的最长距离）。

输入格式：

n
u1 v1 w1
u2 v2 w2
...

其中w是边的权重。

预期输出：

最长路径长度为: X

示例输入：

5
1 2 3
2 3 4
2 4 2
4 5 1

示例输出：

最长路径长度为: 8

提示：可以使用两次DFS的方法，或者直接使用树形DP。

练习2：中等难度 - 计算节点间路径的最大和（中等）

题目描述：给定一棵n个节点的树，每个节点有一个值。请找到一条路径，使得路径上节点值的和最大。

输入格式：

n
val1 val2 ... valn
u1 v1
u2 v2
...

预期输出：

最大路径和为: X

示例输入：

4
5 6 2 3
1 2
2 3
2 4

示例输出：

最大路径和为: 14

（路径：节点1-2-3，和为5+6+2=13，或节点1-2-4，和为5+6+3=14）

练习3：高级难度 - 换根DP应用（困难）

题目描述：给定一棵n个节点的树，每个节点有一个权值。请为每个节点计算：以该节点为根时，所有子树权值和的最大值。

输入格式：

n
val1 val2 ... valn
u1 v1
u2 v2
...

预期输出：n行，每行一个整数，表示以对应节点为根时，所有子树权值和的最大值。

提示：需要使用换根DP，首先计算以某个节点为根时的所有子树权值和，然后通过换根更新其他节点的答案。

常见错误

1. 忘记处理父节点

// 错误：没有检查父节点，导致重复访问
for (int child : tree[node]) {
    // 缺少：if (child == parent) continue;
    dfs(child, node);  // 可能又回到父节点，导致无限递归
}

2. 换根DP中状态转移错误

// 错误：没有正确计算新根的状态
void dfs2(int node, int parent) {
    for (int child : tree[node]) {
        if (child == parent) continue;
        
        // 错误示例：直接修改没有考虑子树大小的变化
        dist_sum[child] = dist_sum[node] - subtree_size[child] + (n - subtree_size[child]);
        // 正确应该是：dist_sum[child] = dist_sum[node] - subtree_size[child] + (n - subtree_size[child]);
    }
}

3. 数组越界

// 错误：没有考虑节点编号从1开始还是从0开始
int dp[MAXN];
// 如果节点编号从1开始，应该确保MAXN足够大

4. 遗漏初始化

// 错误：没有初始化DP数组
void dfs(int node, int parent) {
    // dp[node] 可能包含上次计算的残留值
    // 应该先初始化：dp[node] = 0;
}

5. 全局变量污染

// 错误：多次调用DFS时没有重置全局变量
int ans = 0;  // 全局变量，在多次测试案例中没有重置

小结

  1. 树形DP特点：在树结构上使用动态规划，通常自底向上计算，状态定义为以当前节点为根的子树信息。

  2. 实现模式：使用DFS递归遍历树，先处理子节点，再用子节点信息更新当前节点状态。

  3. 换根DP技巧：解决无根树问题的有效方法，通过两次DFS（第一次计算基础状态，第二次换根更新）实现O(n)时间复杂度。

  4. 常见应用：

    • 树的直径问题
    • 节点间最大路径和
    • 以每个节点为根的某种最优值
    • 树的重心、中心等

  5. 注意事项：

    • 一定要处理父节点，避免循环递归
    • 注意状态定义的正确性
    • 换根DP要注意状态转移的正确计算
    • 注意数组大小和初始化

关键思想：树形DP将复杂问题分解为子树问题，利用树的递归性质进行高效求解。掌握换根DP技巧可以解决很多看似需要O(n²)复杂度的无根树问题。

练习编辑器

rust
Loading...

继续学习

完成本课后，建议继续学习下一课「状态压缩 DP」 以巩固所学知识。