跳转至

樹形 DP

樹形 DP，即在樹上進行的 DP。由於樹固有的遞歸性質，樹形 DP 一般都是遞歸進行的。

基礎

以下面這道題為例，介紹一下樹形 DP 的一般過程。

例題 洛谷 P1352 沒有上司的舞會

某大學有 \(n\) 個職員，編號為 \(1 \sim N\)。他們之間有從屬關係，也就是説他們的關係就像一棵以校長為根的樹，父結點就是子結點的直接上司。現在有個週年慶宴會，宴會每邀請來一個職員都會增加一定的快樂指數 \(a_i\)，但是呢，如果某個職員的直接上司來參加舞會了，那麼這個職員就無論如何也不肯來參加舞會了。所以，請你編程計算，邀請哪些職員可以使快樂指數最大，求最大的快樂指數。

我們設 \(f(i,0/1)\) 代表以 \(i\) 為根的子樹的最優解（第二維的值為 0 代表 \(i\) 不參加舞會的情況，1 代表 \(i\) 參加舞會的情況）。

對於每個狀態，都存在兩種決策（其中下面的 \(x\) 都是 \(i\) 的兒子）：

  • 上司不參加舞會時，下屬可以參加，也可以不參加，此時有 \(f(i,0) = \sum\max \{f(x,1),f(x,0)\}\)；
  • 上司參加舞會時，下屬都不會參加，此時有 \(f(i,1) = \sum{f(x,0)} + a_i\)。

我們可以通過 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <algorithm>
#include <cstdio>
using namespace std;

struct edge {
  int v, next;
} e[6005];

int head[6005], n, cnt, f[6005][2], ans, is_h[6005], vis[6005];

void addedge(int u, int v) {  // 建图
  e[++cnt].v = v;
  e[cnt].next = head[u];
  head[u] = cnt;
}

void calc(int k) {
  vis[k] = 1;
  for (int i = head[k]; i; i = e[i].next) {  // 枚举该结点的每个子结点
    if (vis[e[i].v]) continue;
    calc(e[i].v);
    f[k][1] += f[e[i].v][0];
    f[k][0] += max(f[e[i].v][0], f[e[i].v][1]);  // 转移方程
  }
  return;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &f[i][1]);
  for (int i = 1; i < n; i++) {
    int l, k;
    scanf("%d%d", &l, &k);
    is_h[l] = 1;
    addedge(k, l);
  }
  for (int i = 1; i <= n; i++)
    if (!is_h[i]) {  // 从根结点开始DFS
      calc(i);
      printf("%d", max(f[i][1], f[i][0]));
      return 0;
    }
}

習題

樹上揹包

樹上的揹包問題，簡單來説就是揹包問題與樹形 DP 的結合。

例題 洛谷 P2014 CTSC1997 選課

現在有 \(n\) 門課程，第 \(i\) 門課程的學分為 \(a_i\)，每門課程有零門或一門先修課，有先修課的課程需要先學完其先修課，才能學習該課程。

一位學生要學習 \(m\) 門課程，求其能獲得的最多學分數。

\(n,m \leq 300\)

每門課最多隻有一門先修課的特點，與有根樹中一個點最多隻有一個父親結點的特點類似。

因此可以想到根據這一性質建樹，從而所有課程組成了一個森林的結構。為了方便起見，我們可以新增一門 \(0\) 學分的課程（設這個課程的編號為 \(0\)），作為所有無先修課課程的先修課，這樣我們就將森林變成了一棵以 \(0\) 號課程為根的樹。

我們設 \(f(u,i,j)\) 表示以 \(u\) 號點為根的子樹中，已經遍歷了 \(u\) 號點的前 \(i\) 棵子樹，選了 \(j\) 門課程的最大學分。

轉移的過程結合了樹形 DP 和 揹包 DP 的特點，我們枚舉 \(u\) 點的每個子結點 \(v\)，同時枚舉以 \(v\) 為根的子樹選了幾門課程，將子樹的結果合併到 \(u\) 上。

記點 \(x\) 的兒子個數為 \(s_x\)，以 \(x\) 為根的子樹大小為 \(\textit{siz_x}\)，可以寫出下面的狀態轉移方程：

\[ f(u,i,j)=\max_{v,k \leq j,k \leq \textit{siz_v}} f(u,i-1,j-k)+f(v,s_v,k) \]

注意上面狀態轉移方程中的幾個限制條件，這些限制條件確保了一些無意義的狀態不會被訪問到。

\(f\) 的第二維可以很輕鬆地用滾動數組的方式省略掉，注意這時需要倒序枚舉 \(j\) 的值。

可以證明，該做法的時間複雜度為 \(O(nm)\)1。

參考代碼 
 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
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int f[305][305], s[305], n, m;
vector<int> e[305];

int dfs(int u) {
  int p = 1;
  f[u][1] = s[u];
  for (auto v : e[u]) {
    int siz = dfs(v);
    // 注意下面两重循环的上界和下界
    // 只考虑已经合并过的子树，以及选的课程数超过 m+1 的状态没有意义
    for (int i = min(p, m + 1); i; i--)
      for (int j = 1; j <= siz && i + j <= m + 1; j++)
        f[u][i + j] = max(f[u][i + j], f[u][i] + f[v][j]);  // 转移方程
    p += siz;
  }
  return p;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    int k;
    scanf("%d%d", &k, &s[i]);
    e[k].push_back(i);
  }
  dfs(0);
  printf("%d", f[0][m + 1]);
  return 0;
}

習題

換根 DP

樹形 DP 中的換根 DP 問題又被稱為二次掃描，通常不會指定根結點，並且根結點的變化會對一些值，例如子結點深度和、點權和等產生影響。

通常需要兩次 DFS，第一次 DFS 預處理諸如深度，點權和之類的信息，在第二次 DFS 開始運行換根動態規劃。

接下來以一些例題來帶大家熟悉這個內容。

例題 [POI2008]STA-Station

給定一個 \(n\) 個點的樹，請求出一個結點，使得以這個結點為根時，所有結點的深度之和最大。

不妨令 \(u\) 為當前結點，\(v\) 為當前結點的子結點。首先需要用 \(s_i\) 來表示以 \(i\) 為根的子樹中的結點個數，並且有 \(s_u=1+\sum s_v\)。顯然需要一次 DFS 來計算所有的 \(s_i\)，這次的 DFS 就是預處理，我們得到了以某個結點為根時其子樹中的結點總數。

考慮狀態轉移，這裏就是體現＂換根＂的地方了。令 \(f_u\) 為以 \(u\) 為根時，所有結點的深度之和。

\(f_v\leftarrow f_u\) 可以體現換根，即以 \(u\) 為根轉移到以 \(v\) 為根。顯然在換根的轉移過程中，以 \(v\) 為根或以 \(u\) 為根會導致其子樹中的結點的深度產生改變。具體表現為：

  • 所有在 \(v\) 的子樹上的結點深度都減少了一，那麼總深度和就減少了 \(s_v\)；

  • 所有不在 \(v\) 的子樹上的結點深度都增加了一，那麼總深度和就增加了 \(n-s_v\)；

根據這兩個條件就可以推出狀態轉移方程 \(f_v = f_u - s_v + n - s_v=f_u + n - 2 \times s_v\)。

於是在第二次 DFS 遍歷整棵樹並狀態轉移 \(f_v=f_u + n - 2 \times s_v\)，那麼就能求出以每個結點為根時的深度和了。最後只需要遍歷一次所有根結點深度和就可以求出答案。

參考代碼 
 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

int head[1000010 << 1], tot;
long long n, sz[1000010], dep[1000010];
long long f[1000010];

struct node {
  int to, next;
} e[1000010 << 1];

void add(int u, int v) {  // 建图
  e[++tot] = {v, head[u]};
  head[u] = tot;
}

void dfs(int u, int fa) {  // 预处理dfs
  sz[u] = 1;
  dep[u] = dep[fa] + 1;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v != fa) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}

void get_ans(int u, int fa) {  // 第二次dfs换根dp
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v != fa) {
      f[v] = f[u] - sz[v] * 2 + n;
      get_ans(v, u);
    }
  }
}

int main() {
  scanf("%lld", &n);
  int u, v;
  for (int i = 1; i <= n - 1; i++) {
    scanf("%d%d", &u, &v);
    add(u, v);
    add(v, u);
  }
  dfs(1, 1);
  for (int i = 1; i <= n; i++) f[1] += dep[i];
  get_ans(1, 1);
  long long int ans = -1;
  int id;
  for (int i = 1; i <= n; i++) {  // 统计答案
    if (f[i] > ans) {
      ans = f[i];
      id = i;
    }
  }
  printf("%d\n", id);
  return 0;
}

習題

參考資料與註釋

  1. 子樹合併揹包類型的 dp 的複雜度證明 - LYD729 的 CSDN 博客 ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用