树形 DP

概念讲解

什么是树形 DP？

在树结构上进行的动态规划。

核心思想

自底向上计算，利用子树信息。

经典问题

1. 树的直径

问题： 求树上最长路径。

123456789101112int diameter = 0;

int dfs(int u, int parent) {
    int maxDepth = 0;
    for (int v : graph[u]) {
        if (v == parent) continue;
        int depth = dfs(v, u) + 1;
        diameter = max(diameter, maxDepth + depth);
        maxDepth = max(maxDepth, depth);
    }
    return maxDepth;
}

2. 树的重心

问题： 找一个点，使得删除该点后最大子树最小。

1234567891011121314151617int minSize = 1e9, centroid = 0;

int dfs(int u, int parent, int n) {
    int size = 1, maxSize = 0;
    for (int v : graph[u]) {
        if (v == parent) continue;
        int childSize = dfs(v, u, n);
        size += childSize;
        maxSize = max(maxSize, childSize);
    }
    maxSize = max(maxSize, n - size);
    if (maxSize < minSize) {
        minSize = maxSize;
        centroid = u;
    }
    return size;
}

3. 没有上司的舞会

问题： 选择节点，不能同时选父子节点，求最大权值和。

1234567891011int dp[N][2];  // dp[u][0] 不选 u, dp[u][1] 选 u

void dfs(int u, int parent) {
    dp[u][1] = value[u];
    for (int v : graph[u]) {
        if (v == parent) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

考点分析

初赛考查方式

  1. 程序阅读： 树形 DP
  2. 编程题： 树上问题

常见考点

  • 树的直径
  • 树的重心
  • 换根 DP

例题精讲

例题 1：树的直径

题目： 求树的直径。

解答：

两次 DFS 或一次 DFS 维护最长路径。

练习题

  1. 树形 DP 的核心思想是什么？
查看答案

树形 DP 的核心思想：

  1. 自底向上计算：从叶子节点开始，逐步向上
  2. 利用子树信息：当前节点的答案依赖于子树的答案
  3. DFS 遍历：用 DFS 遍历树，回溯时计算
  1. 如何求树的直径？
查看答案

方法一：两次 DFS

  1. 从任意点 DFS，找到最远点 u
  2. 从 u DFS，找到最远点 v
  3. u 到 v 的距离就是直径

方法二：一次 DFS

1234567891011int diameter = 0;
int dfs(int u, int parent) {
    int maxDepth = 0;
    for (int v : graph[u]) {
        if (v == parent) continue;
        int depth = dfs(v, u) + 1;
        diameter = max(diameter, maxDepth + depth);
        maxDepth = max(maxDepth, depth);
    }
    return maxDepth;
}
  1. 换根 DP 的应用场景是什么？
查看答案

换根 DP 的应用场景：

  1. 求以每个节点为根的某种值：如以每个点为根的深度和
  2. 树的重心：找删除后最大子树最小的点
  3. 树上距离：求每个点到其他点的距离和

核心：先任选一个根计算，再通过换根公式 O(1) 转移到其他根。

易错点

⚠️ 注意：

  1. 要自底向上计算
  2. 注意父子关系
  3. 换根 DP 要维护子树信息
  4. 初始化要正确