Tree DP

Tree DP is DP performed on a tree. Because of the inherent recursive nature of trees, tree DP is generally carried out recursively.

Basics

The following problem illustrates the general process of tree DP.

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

There are two decisions for each state (where each $x$ below is a child of $i$):

• When the supervisor does not attend the party, a subordinate may attend or not attend, so $f(i,0) = \sum\max \{f(x,1),f(x,0)\}$.
• When the supervisor attends the party, none of the subordinates attends, so $f(i,1) = \sum{f(x,0)} + a_i$.

We can update the optimal solution of the current node through DFS when returning to the previous level.

#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 equation
  }
  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 DFS from the root
      calc(i);
      cout << max(f[i][1], f[i][0]);
      return 0;
    }
}

In general, a tree DP state is usually the optimal solution for the current node. First use DFS to traverse all optimal solutions of the subtrees, then pass them upward to the parent node for transitions; the value at the root is ultimately the desired optimal solution.

Exercises

• HDU 2196 Computer

• POJ 1463 Strategic game

• [POI2014]FAR-FarmCraft](https://www.luogu.com.cn/problem/P3574)

Tree knapsack

The knapsack problem on a tree is, simply put, a combination of the knapsack problem and tree DP.

The fact that each course has at most one prerequisite is similar to the fact that each node in a rooted tree has at most one parent.

Therefore, we can build a tree based on this property, so that all courses form a forest. For convenience, add a course worth $0$ credits (numbered $0$) as the prerequisite of every course with no prerequisite; this turns the forest into a tree rooted at course $0$.

Let $f(u,i,j)$ denote the maximum credits obtained in the subtree rooted at node $u$, after the first $i$ subtrees of node $u$ have been traversed and $j$ courses have been selected.

The transition combines the characteristics of tree DP and knapsack DP: enumerate every child $v$ of node $u$, while enumerating the number of courses selected in the subtree rooted at $v$, and merge the subtree result into $u$.

Let the number of children of node $x$ be $s_x$ and the size of the subtree rooted at $x$ be $\textit{siz}_x$. The following transition can be written:

Note the several constraints in the transition above. These constraints ensure that meaningless states are not visited.

The second dimension of $f$ can be omitted easily with a rolling array; note that $j$ must then be enumerated in reverse order.

It can be proved that the time complexity is $O(nm)$¹.

#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 following two loops
    // Only consider already merged subtrees; states selecting more than m+1 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 equation
    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;
}

Exercises

• CTSC1997 Course Selection

• JSOI2018 Infiltration Operation

• SDOI2017 Apple Tree

• Codeforces Round 875 Div. 1 Problem D. Mex Tree

Rerooting DP

The rerooting DP problem in tree DP is also called a two-pass scan. It usually does not specify a root, and changing the root affects values such as the sum of node depths and the sum of node weights.

It usually requires two DFS traversals. The first DFS precomputes information such as depths and sums of node weights, and the second DFS begins the rerooting dynamic programming.

The following examples familiarize you with this topic.

Let $u$ be the current node and $v$ be a child of the current node. First, use $s_i$ to denote the number of nodes in the subtree rooted at $i$; then $s_u=1+\sum s_v$. Clearly, one DFS is needed to calculate every $s_i$. This DFS is the preprocessing step, which obtains the total number of nodes in the subtree when a particular node is used as the root.

Consider the transition; this is where rerooting appears. Let $f_u$ be the sum of the depths of all nodes when $u$ is the root.

The transition $f_v\leftarrow f_u$ represents rerooting, from $u$ as the root to $v$ as the root. During this transition, using $v$ or $u$ as the root changes the depths of nodes in their subtrees. Specifically:

• The depth of every node in the subtree of $v$ decreases by 1, so the total depth sum decreases by $s_v$.

• The depth of every node outside the subtree of $v$ increases by 1, so the total depth sum increases by $n-s_v$.

These two conditions give the transition $f_v = f_u - s_v + n - s_v=f_u + n - 2 \times s_v$.

Thus, perform a second DFS over the entire tree and use the transition $f_v=f_u + n - 2 \times s_v$; this obtains the depth sum for every possible root. Finally, scan all root depth sums once to obtain the answer.

#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) {  // Preprocess 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 for 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++) {  // Compute the answer
    if (f[i] > ans) {
      ans = f[i];
      id = i;
    }
  }
  cout << id << '\n';
  return 0;
}

Exercises

• Atcoder Educational DP Contest, Problem V, Subtree

• Educational Codeforces Round 67, Problem E, Tree Painting

• POJ 3585 Accumulation Degree

• [USACO10MAR]Great Cow Gathering G

• Codeforces 708C Centroids

References and notes