树形动态规划⚓︎

树形动态规划（ $\text{Tree DP}$ ）是动态规划的一种特殊类型，通常用于解决与树结构相关的问题。其核心思想是将树划分为若干个子树，通过递推关系来求解整个树的问题。

一般树形 $\text{DP}$ 根据子节点的状态来更新父节点的状态，或者根据父节点的状态来更新子节点的状态。因此，每个节点定义几种状态，然后根据这些状态进行递归计算。

树形 $\text{DP}$ 的基本思路：

分析父树得到答案需要子树的哪些信息
把子树信息的全集定义成递归返回值
通过递归让子树返回全集信息
整合子树的全集信息得到父树的全集信息并返回

整合子树信息⚓︎

整合子树信息是树形动态规划的关键步骤。假设有一个节点 $u$ ，它有若干个子节点 $v_1, v_2, \ldots, v_k$ 。每个子节点 $v_i$ 都有一个状态值 $dp[v_i]$ ，表示从子节点 $v_i$ 出发的某种最优解。

最大BST子树

给定一个二叉树，找到其中最大的搜索二叉子树（ $\text{BST}$ ），并返回该子树的大小。

Leetcode Premium

C++

#include <functional>
using namespace std;

class TreeNode {
 public:
  int val;
  TreeNode *left;
  TreeNode *right;
};

class Solution {
 public:
  int largestBSTSubtree(TreeNode *root) {
    int max_size = 0;

    // 定义返回值: {是否为BST, 子树大小, 子树最小值, 子树最大值}
    struct Status {
      bool is_bst;
      int size;
      int min;
      int max;
    };

    function<Status(TreeNode *)> dfs = [&](TreeNode *node) -> Status {
      // 空节点视为BST, 大小为0, 最小值为+∞, 最大值为-∞
      if (!node) { return Status{.is_bst = true, .size = 0, .min = INT_MAX, .max = INT_MIN}; }
      auto left  = dfs(node->left);
      auto right = dfs(node->right);
      Status res;
      // 判断当前节点是否为BST
      if (left.is_bst && right.is_bst && node->val > left.max && node->val < right.min) {
        res.is_bst = true;                        // 是BST
        res.size   = left.size + right.size + 1;  // 子树大小
        res.min    = min(left.min, node->val);    // 子树最小值
        res.max    = max(right.max, node->val);   // 子树最大值
        max_size   = max(max_size, res.size);     // 更新最大BST子树大小
      } else {
        res.is_bst = false;                       // 不是BST
        res.size   = max(left.size, right.size);  // 最大BST子树大小
        // 最小值和最大值无意义
      }
      return res;
    };
    dfs(root);
    return max_size;
  }
};

最小点覆盖⚓︎

给定一颗有 $n$ 个点的有根树，从这 $n$ 个点中选出尽量少的点，使得所有边都与取出来的点相连。（点覆盖边）

$f_{u,0}$ 表示以 $u$ 为根的子树中， $u$ 不在点覆盖集中所需要选取的最小点数。因为 $u$ 不选取，则 $u$ 的儿子一定要取。

$f_{u,1}$ 表示以 $u$ 为根的子树中， $u$ 在点覆盖集中所需要选取的最小点数。因为 $u$ 被选取，则 $u$ 的儿子可以选择被覆盖或者不被覆盖。

状态转移如下：

$\begin{aligned} f_{u,0} & = \sum_{v \in \text{children of } u} f_{v,1} \\ f_{u,1} & = \sum_{v \in \text{children of } u} \min(f_{v,0}, f_{v,1}) + 1 \end{aligned}$

战略游戏

给定一棵树，要求选择一些节点，使得每条边至少有一个端点被选择，同时使得被选择的节点数最少。

C++

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

int main() {
  int n;
  cin >> n;
  vector<vector<int>> tree(n);
  vector<int> is_root(n, 1);
  vector<vector<int>> dp(n, vector<int>(2));
  for (int i = 0; i < n; i++) {
    int x, k;
    cin >> x >> k;
    for (int j = 0; j < k; j++) {
      int y;
      cin >> y;
      tree[x].push_back(y);
      is_root[y] = 0;
    }
  }

  function<void(int, int)> dfs = [&](int u, int from) {
    dp[u][0] = 1;
    dp[u][1] = 0;
    for (int v : tree[u]) {
      if (v == from) { continue; }
      dfs(v, u);
      dp[u][0] += dp[v][1];                 // u不选，所以子节点必须选择
      dp[u][1] += min(dp[v][0], dp[v][1]);  // u选, 所以子节点可选可不选
    }
  };
  int root = find(is_root.begin(), is_root.end(), 1) - is_root.begin();
  dfs(root, -1);
  cout << min(dp[root][0], dp[root][1]) << '\n';
  return 0;
}

最大独立集⚓︎

给定一棵有 $n$ 个点的树，从 $n$ 个点中选出尽量多的点，使得两两之间没有连边。

$f_{u,0}$ 表示以 $u$ 为根的子树中， $u$ 不在独立集中所能选取的最大点数。因为 $u$ 不选取，则 $u$ 的儿子可以选择被覆盖或者不被覆盖。

$f_{u,1}$ 表示以 $u$ 为根的子树中， $u$ 在独立集中所能选取的最大点数。因为 $u$ 被选取，则 $u$ 的儿子一定不选。

状态转移如下：

$\begin{aligned} f_{u,0} & = \sum_{v \in \text{children of } u} \max(f_{v,0}, f_{v,1}) \\ f_{u,1} & = \sum_{v \in \text{children of } u} f_{v,0} + 1 \end{aligned}$

没有上司的舞会

有一个公司共有 $n$ 名员工，每个员工都有一个快乐值。为了举办一场舞会，公司决定邀请一些员工参加，但有一个规定：如果某个员工参加了，那么他的直接下属就不能参加。现在给出每个员工的快乐值以及他们之间的上下级关系，问如何安排才能使得参加舞会的员工的快乐值总和最大。

C++

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

int main() {
  int n;
  cin >> n;
  vector<vector<int>> tree(n + 1);
  vector<int> happiness(n + 1);
  vector<int> is_root(n + 1, 1);
  // dp[i][0]: i不被子节点覆盖的最大快乐值
  // dp[i][1]: i被子节点覆盖的最大快乐值
  vector<vector<int>> dp(n + 1, vector<int>(2));
  for (int i = 1; i <= n; i++) { cin >> happiness[i]; }
  for (int i = 1; i < n; i++) {
    int l, k;
    cin >> l >> k;
    tree[k].push_back(l);
    is_root[l] = 0;
  }

  function<void(int, int)> dfs = [&](int u, int from) {
    dp[u][0] = 0;
    dp[u][1] = happiness[u];
    for (int v : tree[u]) {
      if (v == from) { continue; }
      dfs(v, u);
      dp[u][0] += max(dp[v][0], dp[v][1]);  // 选择不来，所以子节点可以选择来或不来
      dp[u][1] += dp[v][0];                 // 选择来，所以子节点必须选择不来
    }
  };

  int root = find(is_root.begin() + 1, is_root.end(), 1) - is_root.begin();
  dfs(root, 0);

  cout << max(dp[root][0], dp[root][1]) << '\n';
  return 0;
}

最小支配集⚓︎

给定一棵 $n$ 个点的树，从 $n$ 个点中选取尽量少的点，使得任意一个不在支配集中的点都和一个在支配集中的点有连边。（点覆盖点）

$f_{u,0}$ 表示以 $u$ 为根的子树中， $u$ 在支配集中所需要选取的最小点数。因为 $u$ 选取，则 $u$ 的儿子可以选择被覆盖或者不被覆盖。（被自己支配）

$f_{u,1}$ 表示以 $u$ 为根的子树中， $u$ 不在支配集但 $u$ 的子节点在支配集中所需要选取的最小点数。因为 $u$ 不选取，则 $u$ 的儿子至少有一个被选取被自己覆盖。对于其他子节点，可以选择被覆盖或者不被覆盖。（被儿子支配）

$f_{u,2}$ 表示以 $u$ 为根的子树中， $u$ 不在支配集但 $u$ 的父节点在支配集中所需要选取的最小点数。因为 $u$ 不选取，则 $u$ 的儿子只能被自己覆盖或者被它的儿子覆盖。（被父亲支配）

状态转移如下：

$\begin{aligned} f_{u,0} & = \sum_{v \in \text{children of } u} \min(f_{v,0}, f_{v,1}, f_{v,2}) + 1 \\ f_{u,1} & = \min_{t \in \text{children of } u} \left( f_{t,0} + \sum_{son \neq t} \min(f_{son,0}, f_{son,1}) \right) \\ f_{u,2} & = \sum_{v \in \text{children of } u} \min(f_{v,0}, f_{v,1}) \end{aligned}$

优化说明：在第二种状态中（被儿子支配），为了找到最优的覆盖方案，考虑子节点 $t$ 作为被自己覆盖的最优子节点，对比另一个非最优的子节点 $v$ ：

$dp[t][0] + \sum_{son \neq t} \min(dp[son][0], dp[son][1]) \lt dp[v][0] + \sum_{son \neq v} \min(dp[son][0], dp[son][1])$

这等价于：

$\sum_{son } \min(dp[son][0], dp[son][1]) + dp[t][0] - \min(dp[t][0], dp[t][1]) < \sum_{son } \min(dp[son][0], dp[son][1]) + dp[v][0] - \min(dp[v][0], dp[v][1])$

即最优子节点 $t$ 满足：

$\forall v \neq t: \quad dp[t][0] - \min(dp[t][0], dp[t][1]) < dp[v][0] - \min(dp[v][0], dp[v][1])$

利用这个性质，先计算所有子节点第一项的贡献，找到最优的子节点作为覆盖自己的节点，再加上这个节点的差值即可。

Cell Phone Network G

给定一棵有 $n$ 个点的树，从 $n$ 个点中选出尽量少的点，使得每个点都被选中的点支配，即每个未被选中的点都至少与一个被选中的点相邻。

叶节点初始化

叶节点没有子节点，因此「被子节点覆盖」这个状态不可能出现，因此在叶节点的情况下，dp[u][1] 的值应该被初始化为 INT_MAX。这样可以确保在计算父节点的状态时，不会错误地选择叶节点作为覆盖自己的子节点。

树可能是无向边，所以不能根据度数判断叶节点，可以根据是否收集到了子节点来确定。

C++

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

int main() {
  int n;
  cin >> n;
  vector<vector<int>> tree(n + 1);
  vector<vector<int>> dp(n + 1, vector<int>(3));
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    tree[x].push_back(y);
    tree[y].push_back(x);
  }

  auto metric = [&](int i) { return dp[i][0] - min(dp[i][0], dp[i][1]); };

  auto dfs    = [&](auto &&self, int u, int from) -> void {
    dp[u][0]       = 1;   // 被自己覆盖
    dp[u][1]       = 0;   // 被子节点覆盖
    dp[u][2]       = 0;   // 被父节点覆盖
    int best_child = -1;  // 选择哪个子节点覆盖自己

    for (int v : tree[u]) {
      if (v == from) { continue; }
      self(self, v, u);
      // 节点被自己覆盖, 则子节点可以选择被自己覆盖或者被父节点覆盖,
      // 或者被自己的子节点覆盖
      dp[u][0] += min({dp[v][0], dp[v][1], dp[v][2]});
      // 节点被子节点覆盖, 则必须选择一个最优的子节点覆盖自己
      dp[u][1] += min(dp[v][0], dp[v][1]);
      if (best_child == -1 || metric(v) < metric(best_child)) { best_child = v; }
      // 节点被父节点覆盖, 则子节点必须选择被自己覆盖或者被子节点覆盖
      dp[u][2] += min(dp[v][0], dp[v][1]);
    }
    // 公式最后的差值。如果没有子节点，则无法被子节点覆盖，因此设为无穷大
    dp[u][1] = (best_child == -1 ? INT_MAX : dp[u][1] + metric(best_child));
  };
  dfs(dfs, 1, 0);
  // 根节点没有父节点, 所以不能被父节点覆盖
  cout << min(dp[1][0], dp[1][1]) << '\n';
  return 0;
}

树上背包⚓︎

给定一棵有 $n$ 个点的树，每个点有一个重量 $w_i$ 和一个价值 $v_i$ ，以及一个背包容量 $C$ 。从 $n$ 个点中选出一些点，使得选中点的总重量不超过 $C$ ，且总价值最大。一般选择子节点也要选择父节点。

定义 $dp[u][j]$ 表示以 $u$ 为根的子树中，选取的点的总重量不超过 $j$ 时的最大价值。状态转移如下：

对于每个子节点 $v \in \text{children}(u)$ ：

若当前正在把子节点 $v$ 合并到 $u$ ，则标准转移可写为：

$dp[u][j] = \max_{0 \le k \le j} \big( dp[u][j],\; dp[u][j-k] + dp[v][k] \big)$

其中 dp[u][j-k] 表示尚未合并 v 时的结果，dp[v][k] 表示分配给子树 v 的容量贡献。若题目要求“选子节点必须选父节点”，通常还需要先用 u 自身的重量和价值初始化 dp[u]。

选课

有 $n$ 门课程，每门课程有一个学分和一个价值。某些课程有先修课程关系，必须先修完先修课程才能选修该课程。现在有 $m$ 个学分，问如何选课使得总价值最大。

C++

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> tree(n + 1);
  vector<int> weights(n + 1, 1);
  vector<int> values(n + 1);
  for (int i = 1; i <= n; i++) {
    int k, s;
    cin >> k >> s;
    tree[k].push_back(i);
    values[i] = s;
  }
  weights[0] = values[0] = 0;  // 根节点重量和价值为0

  vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  function<void(int, int)> dfs = [&](int u, int from) {
    // 初始化: 只放入当前节点
    for (int j = weights[u]; j <= m; ++j) { dp[u][j] = values[u]; }
    for (int v : tree[u]) {
      if (v == from) { continue; }
      dfs(v, u);
      // 将子节点的物品合并到当前节点的背包中, 01背包倒序枚举，完全背包正序枚举
      for (int j = m; j >= weights[u]; --j) {        // 当前背包容量
        for (int k = 0; k <= j - weights[u]; ++k) {  // 分配给当前子树的容量
          dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
        }
      }
    }
  };
  dfs(0, -1);
  cout << dp[0][m] << '\n';

  return 0;
}

上下界优化⚓︎

假设用 $size[u]$ 表示 $u$ 及其所有子树的总重量（已遍历到子节点 $v$ 时，不包括 $v$ 的子树重量）；用 $size[v]$ 表示子节点 $v$ 及其所有子树的总重量（已计算完毕）。

对于 $j$ （当前背包容量）：
- 上界：枚举 $j > size[u] + size[v]$ 时，最优解已经蕴含在 $j = size[u] + size[v]$ 的情况中, 因为再多的容量也装不下更多物品，结果不会变化
  
  上界可以缩小为 $j = min(size[u] + size[v], capacity)$
- 结果：如果背包容量 $m$ 能装下全部物品， $dp[root][size[root]]$ 即为结果，综合即 $dp[root][min(size[root], capacity)]$
对于 $k$ （分配给子节点 $v$ 的容量）：
- 上界：枚举 $k > size[v]$ 时，最优解已经蕴含在 $k = size[v]$ 的情况中，因为分配再多的容量也装不下更多物品，结果不会变化
  
  上界可以缩小为 $k = min(size[v], j - weight[u])$
- 下界：给子节点分配 $0$ 容量时结果不变，可以从 $1$ 开始枚举
  
  当可用容量 $j$ 很大时，可以直接从 $j - size[u]$ 开始枚举，因为当前节点之前的物品已经分配完毕，剩余容量都可以分配给子节点 $v$
  
  下界可以扩大为 $k = max(1, j - size[u])$

时间复杂度

原始状态转移的时间复杂度为 $O(n \cdot C^2)$
优化后的时间复杂度为 $O(n \cdot C)$

选课

C++

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> tree(n + 1);
  vector<int> weights(n + 1, 1);
  vector<int> values(n + 1);
  for (int i = 1; i <= n; i++) {
    int k, s;
    cin >> k >> s;
    tree[k].push_back(i);
    values[i] = s;
  }
  weights[0] = values[0] = 0;  // 根节点重量和价值为0

  vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  vector<int> size(n + 1, 0);  // size[u]: u及其子树的总重量

  function<void(int, int)> dfs = [&](int u, int from) {
    size[u] = weights[u];
    for (int j = weights[u]; j <= m; ++j) { dp[u][j] = values[u]; }
    for (int v : tree[u]) {
      if (v == from) { continue; }
      dfs(v, u);
      int upper_j = min(size[u] + size[v], m);
      for (int j = upper_j; j >= weights[u]; --j) {  // 当前背包容量
        for (int k = max(1, j - size[u]); k <= min(size[v], j - weights[u]); ++k) {
          dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
        }
      }
      size[u] += size[v];
    }
  };
  dfs(0, -1);
  cout << dp[0][min(size[0], m)] << "\n";

  return 0;
}

DFN序优化⚓︎

通过对树进行深度优先搜索（ $\text{DFS}$ ），可以将树的节点按照访问顺序线性化，形成一个数组。这种线性化的表示方式称为深度优先编号（ $\text{DFN}$ ）序。利用 $\text{DFN}$ 序，可以将树形 $\text{DP}$ 问题转化为线性 $\text{DP}$ 问题。

$u$ 是 $\text{DFN}$ 序中第 $i$ 个节点， $size[i]$ 是以 $u$ 为根的子树大小。 $dp[i][j]$ 表示从 $\text{DFN}$ 序中第 $i$ 个节点开始选，背包容量为 $j$ 时的最大价值。分成两种情况：

选择当前节点 $u$ ，则子树中可以选择放入，问题变成从 $i+1$ 个节点开始选，容量为 $j - weight[u]$ 的背包
不选择当前节点 $u$ ，则子树中所有节点都不放入，所以跳过子树大小个节点

利用 $\text{DFN}$ 序以及子树大小，可以将树形 $\text{DP}$ 的状态转移优化为：

$dp[i][j] = \max \big( dp[i + 1][j - weight[u]] + value[u],\; dp[i + size[i]][j] \big)$

时间复杂度

使用 $\text{DFN}$ 优化的时间复杂度为 $O(n \cdot C)$

选课

C++

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> weights(n + 1, 1), values(n + 1);
  vector<vector<int>> tree(n + 1);
  for (int i = 1; i <= n; ++i) {
    int k, s;
    cin >> k >> s;
    tree[k].push_back(i);
    values[i] = s;
  }
  weights[0] = values[0] = 0;  // 根节点重量和价值为0

  vector<int> dfn(n + 1);      // DFN序对应的原始节点编号
  vector<int> size(n + 1, 0);  // 以DFN序计算的子树大小
  int timer = -1;
  // 计算DFN和子树大小
  function<int(int, int)> compute_dfn_size = [&](int u, int from) {
    int dfn_u   = ++timer;  // 当前节点在DFN序中的位置
    dfn[dfn_u]  = u;        // 记录DFN序
    size[dfn_u] = 1;        // 初始化子树大小为1
    for (int v : tree[u]) {
      if (v == from) { continue; }
      size[dfn_u] += compute_dfn_size(v, u);  // 累加子树大小
    }
    return size[dfn_u];
  };
  compute_dfn_size(0, -1);

  // dp[i][j]: 前i个节点, 在容量为j的背包中能获得的最大价值, 0-n 共n+1个节点
  vector<vector<int>> dp(n + 2, vector<int>(m + 1, 0));
  for (int i = n; i >= 0; --i) {             // 逆序枚举DFN序节点
    int u  = dfn[i];                         // 当前节点
    int sz = size[i];                        // 当前节点的子树大小
    for (int j = m; j >= weights[u]; --j) {  // 当前背包容量
      // 放入当前节点, 则子树中可以选择放入, 问题变成从i+1个节点开始选,
      // 容量为j-weights[u]的背包
      dp[i][j] = max(dp[i][j], dp[i + 1][j - weights[u]] + values[u]);
      // 不放入当前节点, 则子树中所有节点都不放入, 所以跳过子树大小个节点
      dp[i][j] = max(dp[i][j], dp[i + sz][j]);
    }
  }
  cout << dp[0][m] << "\n";

  return 0;
}

换根 DP⚓︎

换根 $\text{DP}$ 是树形动态规划中的一种技巧，主要用于解决需要计算树中每个节点作为根节点时的某种最优解的问题。其核心思想是通过两次深度优先搜索（ $\text{DFS}$ ）来实现。

第一次 $\text{DFS}$ 用于计算以某个节点为根的子树的状态值，第二次 $\text{DFS}$ 用于将这些状态值传递到其他节点，从而计算出每个节点作为根节点时的状态值。

树中距离之和

给定一个无向连通树，计算每个节点到其他所有节点的距离之和。

C++

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

class Solution {
 public:
  vector<int> sumOfDistancesInTree(int n, vector<vector<int>> &edges) {
    vector<vector<int>> tree(n);
    for (vector<int> &edge : edges) {
      int x = edge[0], y = edge[1];
      tree[x].emplace_back(y);
      tree[y].emplace_back(x);
    }

    vector<int> size(n, 1);  // 子树的大小,包括自身
    vector<int> ans(n);

    function<void(int, int, int)> dfs1 = [&](int u, int from, int depth) {
      ans[0] += depth;  // 计算根节点的距离和
      for (int child : tree[u]) {
        if (child != from) {
          dfs1(child, u, depth + 1);
          size[u] += size[child];
        }
      }
    };
    dfs1(0, -1, 0);

    function<void(int, int)> dfs2 = [&](int u, int from) {
      for (int v : tree[u]) {
        if (v != from) {
          // 换根时size[v]个节点距离减少1,其余节点距离增加1
          ans[v] = ans[u] - size[v] + (n - size[v]);
          dfs2(v, u);
        }
      }
    };
    dfs2(0, -1);
    return ans;
  }
};

树形动态规划⚓︎

整合子树信息⚓︎

最小点覆盖⚓︎

最大独立集⚓︎

最小支配集⚓︎

树上背包⚓︎

上下界优化⚓︎

DFN序优化⚓︎

换根 DP⚓︎

评论