红魔咖啡馆


头发越掉越多，头发越掉越少

【动态规划】树形DP

  • ~4.69K 字
  1. 1. 树形DP
    1. 1.1. 基本思想
    2. 1.2. 模板
    3. 1.3. 换根DP
      1. 1.3.1. 使用场景
      2. 1.3.2. 核心思想
      3. 1.3.3. 模板
    4. 1.4. 树上背包
      1. 1.4.1. 核心思想
      2. 1.4.2. 分析
        1. 1.4.2.1.
      3. 1.4.3. 状态转移方程
      4. 1.4.4. 例
        1. 1.4.4.1. 优化1
        2. 1.4.4.2. 优化2
        3. 1.4.4.3. DFS序

树形DP

树形dp是在树结构上进行动态规划的方法，通过从叶子节点到根节点（或相反）进行状态转移来解决问题

基本思想

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

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> tree[N];  // 邻接表存树
int dp[N];            // DP状态数组
void dfs(int u, int fa) {
    // 初始化当前节点的状态
    dp[u] = val[u];  // 或其他初始值
    
    // 遍历所有子节点
    for (int v : tree[u]) {
        if (v != fa) {  // 避免回到父节点
            dfs(v, u);  // 递归处理子树
            
            // 状态转移（根据具体问题）
            dp[u] += dp[v];  // 例如：累加子树贡献
        }
    }
    
    // 可以在这里进行一些后处理操作
}

换根DP

换根DP适用于处理以每个节点为根时的情况

使用场景

  • 求每个节点作为根时的某个值
    • 每个节点的子树大小
    • 每个节点到其他所有节点的距离和
    • 每个节点为根时的最大独立集
  • 涉及整棵树的全局信息
    • 树的直径
    • 树的重心

核心思想

通常使用两个DFS：

  • 第一个dfs以1为根，计算每个节点的子树内的信息，从而得到以节点1为根时的答案
  • 第二个dfs进行换根，将根从父节点移动到子节点，更新相关信息并计算新根答案

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 第一遍DFS：计算以1为根的信息
void dfs1(int u, int fa) {
    // 初始化状态
    for (int v : tree[u]) {
        if (v != fa) {
            dfs1(v, u);
            // 更新u的状态基于v的信息
        }
    }
}

// 第二遍DFS：换根计算所有节点答案
void dfs2(int u, int fa) {
    // 计算当前节点的答案
    ans[u] = ...;
    
    for (int v : tree[u]) {
        if (v != fa) {
            // 换根公式：从u换到v
            // 更新v的向上信息
            dfs2(v, u);
        }
    }
}

树上背包

树上背包是在树形结构上应用背包思想，用于解决树的子树中进行资源分配，选择限制等问题

本质是在每个节点的子树中进行背包选择，将子树的结果合并到当前节点

核心思想

  1. DFS遍历：从叶子节点向根节点进行

  2. 子树合并：将每个子树的背包结果合并

  3. 状态转移：在容量限制下选择最优组合

    对于考虑某个子树的根节点x，有两个选择：

    • 不选自己
    • 选自己，考虑自己的子树

分析

给定一棵个节点的有根树，编号为1到 ，1号点为根节点且每个节点有价值，体积 。背包容量为，在满足如果选了，则其所有祖先都要选的限制下，使选择的物品组合总价值和最大。

定义为在根节点x中，选择j个节点的最大值，根据两个选择：

  • 若不选自己，则

  • 若选自己，则

    即根节点的价值+子节点a中选个节点的最大值

这样转移较为麻烦，我们可以将根节点与其孩子看作一个集合，把里面每个点看作物品，问题就转化为了上面所述问题

  • 若为根节点：当前
  • 若为子节点：子树大小大小

不选的大小选

，取max

状态转移方程

$$ { 的孩子数根节点价值

. $$

例

洛谷P2014 选课

使用树建模，把每门课与自己的直接先修课连一条边

使用树上背包进行求解

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n, m;
int val[N];
int dp[N][N][N];
vector<int> g[N];
void dfs(int u){
  for (auto v:g[u]){
    dfs(v);
  }
  dp[u][1][0] = 0;
  dp[u][1][1] = val[u];
  for (int i = 2; i<=g[u].size()+1;i++){
    int v = g[u][i-2];
    for (int j = 0; j<=n; j++){
      for (int k = 0; k<j;k++){
        dp[u][i][j] = max(dp[u][i][j], dp[v][g[v].size()+1][k]+dp[u][i-1][j-k]);
      }
    }
  }
}
void solve() {
  
  cin >> n >>m;
  for (int i = 1; i<=n; i++){
    int u;
    cin >> u >> val[i];
    g[u].push_back(i);


  }
  dfs(0);
  cout << dp[0][g[0].size()+1][m+1];
  
}

优化1

当我们计算时，使用的是前i个物品的节点个数，即前i个子树大小之和

故我们可以将dfs放入主循环，同时记录子树大小

将j的循环终止条件设为子树大小

时间复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int n, m;
int val[N];
int dp[N][N][N];
int cnt[N];
vector<int> g[N];
void dfs(int u){
  cnt[u] = 1;
  dp[u][1][0] = 0;
  dp[u][1][1] = val[u];
  for (int i = 2; i<=g[u].size()+1;i++){
    int v = g[u][i-2];
    dfs(v);
    cnt[u] +=cnt[v]; // 记录子树大小
    
    for (int j = 0; j<=cnt[u]; j++){
      for (int k = 0; k<min(cnt[v]+1,j);k++){ // k不超过子节点子树大小
        dp[u][i][j] = max(dp[u][i][j], dp[v][g[v].size()+1][k]+dp[u][i-1][j-k]);
      }
    }
  }
}
void solve() {
  
  cin >> n >>m;
  for (int i = 1; i<=n; i++){
    int u;
    cin >> u >> val[i];
    g[u].push_back(i);


  }
  dfs(0);
  cout << dp[0][g[0].size()+1][m+1];
}

优化2

更改递推方式：

求当前问题时使用已经求过的答案 -> 用已经求好的答案更新未来的问题

的孩子数

同时可以用滚动数组优化空间复杂度

时间复杂度：

证明略，见视频

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n, m;
int val[N];
int dp[N][N];
int cnt[N];
vector<int> g[N];
void dfs(int u){
  cnt[u] = 1;
  dp[u][0] = 0;
  dp[u][1] = val[u];
  for (int i = 1; i<g[u].size()+1;i++){
    int v = g[u][i-1];
    dfs(v);
    
    
    for (int j = cnt[u]; j>=0; j--){
      for (int k = cnt[v]; k>=0;k--){
        if(k==0||j>0) dp[u][j+k] = max(dp[u][j+k], dp[v][k]+dp[u][j]);
      }
    }
    cnt[u] +=cnt[v];
  }
}
void solve() {
  
  cin >> n >>m;
  for (int i = 1; i<=n; i++){
    int u;
    cin >> u >> val[i];
    g[u].push_back(i);
  }
  dfs(0);
  cout << dp[0][m+1];
}

DFS序

我们采用后序遍历来遍历树，则有着特殊的性质：

  1. 孩子在自己的前面
  2. 第一个孩子 = 自己的编号-1
  3. 第二个孩子 = 自己的编号-第一个孩子的大小
  4. 自己的编号-自己的大小 = 自己兄弟的编号

我们设是考虑当前节点i和自己前面兄弟中选择j个节点的最大值

x是后序遍历编号i对于原来的节点编号

则状态转移方程为： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int n, m;
int val[N];
int dp[N][N];
int cnt[N];
int num[N];
int tot = 0;
vector<int> g[N];
void dfs(int u){
  cnt[u] = 1;
  for(auto v: g[u]){
    dfs(v);
    cnt[u]+=cnt[v];
  }
  num[++tot] = u;
}
void solve() {
  
  cin >> n >>m;
  for (int i = 1; i<=n; i++){
    int u;
    cin >> u >> val[i];
    g[u].push_back(i);
  }
  dfs(0);
  for (int i = 1; i<=n; i++){
    for (int j = 0; j<=m; j++){
      if(j>0) dp[i][j] = max(dp[i-1][j-1]+val[num[i]], dp[i-cnt[num[i]]][j]);
    }
  }
  cout << dp[n][m];
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
赞助喵
非常感谢您的喜欢！
赞助喵