Skip to content

Tree DP

Tree DP is DP carried out on a tree. Because a tree is inherently recursive, tree DP is usually done by recursion.

Basics

The following problem shows how tree DP usually goes.

Example: Luogu P1352 A Party Without the Boss

A university has \(n\) employees, numbered \(1 \sim n\). They are organized in a hierarchy: their relations form a tree rooted at the president, in which every parent is the direct superior of its children. An anniversary party is coming up, and every employee who is invited adds a certain happiness index \(a_i\). However, if an employee's direct superior comes to the party, that employee will refuse to come no matter what. Write a program that works out which employees to invite so that the happiness index is as large as possible, and find this maximum.

Let \(f(i,0/1)\) be the optimal solution for the subtree rooted at \(i\) (the second dimension is 0 when \(i\) does not attend the party and 1 when \(i\) attends).

Every state has two decisions (below, \(x\) always stands for a child of \(i\)):

  • If the superior does not attend, each subordinate may or may not attend, so \(f(i,0) = \sum\max \{f(x,1),f(x,0)\}\).
  • If the superior attends, no subordinate attends, so \(f(i,1) = \sum{f(x,0)} + a_i\).

We run a DFS and update the optimal solution of the current node when the recursion returns to the level above.

 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
#include <algorithm>
#include <iostream>
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) {  // build the graph
  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) {  // enumerate every child of this node
    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]);  // transition
  }
  return;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> f[i][1];
  for (int i = 1; i < n; i++) {
    int l, k;
    cin >> l >> k;
    is_h[l] = 1;
    addedge(k, l);
  }
  for (int i = 1; i <= n; i++)
    if (!is_h[i]) {  // start the DFS from the root
      calc(i);
      cout << max(f[i][1], f[i][0]);
      return 0;
    }
}

The state in tree DP is usually the optimal solution for the current node. A DFS first works out the optimal solutions of all the subtrees, which are then passed up to each subtree's parent for the transition. The value at the root is the optimal solution we are after.

Practice problems

Tree knapsack

A knapsack problem on a tree is, simply put, a knapsack problem combined with tree DP.

Example: Luogu P2014 CTSC1997 Course Selection

There are \(n\) courses. Course \(i\) is worth \(a_i\) credits, and every course has zero or one prerequisite. A course with a prerequisite can be taken only after the prerequisite has been completed.

A student is going to take \(m\) courses. Find the maximum number of credits the student can earn.

\(n,m \leq 300\)

Each course has at most one prerequisite, just as each node of a rooted tree has at most one parent.

This suggests building a tree from that property, so that the courses form a forest. For convenience, add a course worth \(0\) credits (number it \(0\)) and make it the prerequisite of every course that has none. The forest then becomes a tree rooted at course \(0\).

Let \(f(u,i,j)\) be the maximum number of credits in the subtree rooted at node \(u\) when the first \(i\) subtrees of \(u\) have been traversed and \(j\) courses have been chosen.

The transition combines features of tree DP and knapsack DP: enumerate every child \(v\) of \(u\) and, together with it, the number of courses chosen in the subtree rooted at \(v\), and merge the result of that subtree into \(u\).

Let \(s_x\) be the number of children of node \(x\) and \(\textit{siz}_x\) the size of the subtree rooted at \(x\). This gives the recurrence:

\[ 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) \]

Note the constraints in the recurrence above: they make sure that certain meaningless states are never visited.

The second dimension of \(f\) is easy to drop with a rolling array. If you do so, enumerate \(j\) in decreasing order.

It can be shown that this approach runs in \(O(nm)\) time1.

Reference code
 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
#include <algorithm>
#include <iostream>
#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);
    // note the upper and lower bounds of the two nested loops below
    // only subtrees already merged are considered, and states with more than m+1 chosen courses are meaningless
    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]);  // transition
    p += siz;
  }
  return p;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    int k;
    cin >> k >> s[i];
    e[k].push_back(i);
  }
  dfs(0);
  cout << f[0][m + 1];
  return 0;
}

Practice problems

Rerooting DP

Rerooting DP, a kind of tree DP, is also known as the two-pass scan. The problem usually does not specify a root, and changing the root affects certain values, such as the sum of the depths of the child nodes or the sum of the vertex weights.

It usually takes two DFS passes. The first precomputes information such as depths and sums of vertex weights; the second runs the rerooting dynamic programming.

We now work through some example problems to get familiar with it.

Example: [POI2008] STA-Station

Given a tree with \(n\) nodes, find a node such that the sum of the depths of all nodes is largest when the tree is rooted at that node.

Let \(u\) be the current node and \(v\) a child of the current node. First, let \(s_i\) be the number of nodes in the subtree rooted at \(i\); then \(s_u=1+\sum s_v\). Computing all the \(s_i\) clearly takes one DFS. This DFS is the preprocessing: it gives the number of nodes in every subtree when the tree is rooted at some particular node.

Now for the state transition, which is where the rerooting comes in. Let \(f_u\) be the sum of the depths of all nodes when the tree is rooted at \(u\).

\(f_v\leftarrow f_u\) expresses the rerooting: we move from the tree rooted at \(u\) to the tree rooted at \(v\). Clearly, in this transition, rooting the tree at \(v\) instead of \(u\) changes the depths of the nodes in their subtrees. Specifically:

  • The depth of every node in the subtree of \(v\) decreases by one, so the total depth decreases by \(s_v\).

  • The depth of every node outside the subtree of \(v\) increases by one, so the total depth increases by \(n-s_v\).

These two facts give the recurrence \(f_v = f_u - s_v + n - s_v=f_u + n - 2 \times s_v\).

So the second DFS traverses the whole tree and applies the transition \(f_v=f_u + n - 2 \times s_v\), which yields the sum of depths for every choice of root. One final pass over the sums of depths of all the roots gives the answer.

Reference code
 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
61
#include <iostream>
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) {  // build the graph
  e[++tot] = {v, head[u]};
  head[u] = tot;
}

void dfs(int u, int fa) {  // preprocessing 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) {  // second DFS: the rerooting 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() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  int u, v;
  for (int i = 1; i <= n - 1; i++) {
    cin >> 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++) {  // collect the answer
    if (f[i] > ans) {
      ans = f[i];
      id = i;
    }
  }
  cout << id << '\n';
  return 0;
}

Practice problems

References and notes