Skip to content

Dynamic DP

Dynamic DP is a technique introduced by Cat Kun at WC2018, generally used to solve DP problems on trees with point weight (or edge weight) modification operations.

Example

Let's explain the process of dynamic DP using this template problem as an example.

Example Luogu P4719【Template】Dynamic DP

Given a tree with \(n\) vertices, each vertex has a weight. There are \(m\) operations, each operation gives \(x,y\) indicating that the weight of vertex \(x\) is modified to \(y\). After each operation, you need to output the weight of the maximum weight independent set of the tree.

Generalized Matrix Multiplication

Define generalized matrix multiplication \(A\times B=C\) as:

\[ C_{i,j}=\max_{k=1}^{n}(A_{i,k}+B_{k,j}) \]

This is equivalent to replacing multiplication with addition and addition with \(\max\) operation in ordinary matrix multiplication.

Generalized matrix multiplication also satisfies the associative property, so matrix exponentiation can be used.

Without Modification Operations

Let \(f_{i,0}\) denote the maximum answer when not selecting \(i\), and \(f_{i,1}\) denote the maximum answer when selecting \(i\).

Then the DP equations are:

\[ \begin{cases}f_{i,0}=\sum_{son}\max(f_{son,0},f_{son,1})\\f_{i,1}=w_i+\sum_{son}f_{son,0}\end{cases} \]

The answer is \(\max(f_{root,0},f_{root,1})\).

With Modification Operations

First, perform heavy-light decomposition on the tree. Suppose we have a heavy chain like this:

Let \(g_{i,0}\) denote the maximum answer when not selecting \(i\) and only allowing selection from the subtrees of \(i\)'s light children, and \(g_{i,1}\) denote the maximum answer when selecting \(i\) without considering \(son_i\), where \(son_i\) is the heavy child of \(i\).

Assuming we know \(g_{i,0/1}\), then the DP equations are:

\[ \begin{cases}f_{i,0}=g_{i,0}+\max(f_{son_i,0},f_{son_i,1})\\f_{i,1}=g_{i,1}+f_{son_i,0}\end{cases} \]

The answer is \(\max(f_{root,0},f_{root,1})\).

We can construct the matrix:

\[ \begin{bmatrix} g_{i,0} & g_{i,0}\\ g_{i,1} & -\infty \end{bmatrix}\times \begin{bmatrix} f_{son_i,0}\\f_{son_i,1} \end{bmatrix}= \begin{bmatrix} f_{i,0}\\f_{i,1} \end{bmatrix} \]

Note that we are using the generalized multiplication rule here.

It can be observed that during modification operations, we only need to update \(g_{i,1}\) and each upward heavy chain.

Detailed Approach

  1. Perform DFS preprocessing to compute \(f_{i,0/1}\) and \(g_{i,0/1}\).

  2. Perform heavy-light decomposition on the tree (note: since querying a point requires computing the interval matrix product from that point to the end of its heavy chain, record \(End_i\) for each point, representing the end node ID of the heavy chain containing \(i\)). Build a segment tree for each heavy chain, maintaining the \(g\) matrix and the interval product of \(g\) matrices.

  3. During modification, first update \(g_{i,1}\) and the matrix at node \(i\) in the segment tree, compute the change in the matrix of \(top_i\), and propagate the modification to the matrix of \(fa_{top_i}\).

  4. Querying involves computing the interval product from 1 to the end of its heavy chain, and finally taking a \(\max\).

Code Implementation 

  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
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
```cpp
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

constexpr int MAXN = 500010;
constexpr int INF = 0x3f3f3f3f;

int Begin[MAXN], Next[MAXN], To[MAXN], e, n, m;
int sz[MAXN], son[MAXN], top[MAXN], fa[MAXN], dis[MAXN], p[MAXN], id[MAXN],
    End[MAXN];
// p[i] represents the new index of node i after tree decomposition, id[p[i]] = i
int cnt, tot, a[MAXN], f[MAXN][2];

struct matrix {
  int g[2][2];

  matrix() { memset(g, 0, sizeof(g)); }

  matrix operator*(const matrix &b) const  // Overload matrix multiplication
  {
    matrix c;
    for (int i = 0; i <= 1; i++)
      for (int j = 0; j <= 1; j++)
        for (int k = 0; k <= 1; k++)
          c.g[i][j] = max(c.g[i][j], g[i][k] + b.g[k][j]);
    return c;
  }
} Tree[MAXN], g[MAXN];  // Tree[] is the built segment tree, g[] is the matrix maintained for each node

void PushUp(int root) { Tree[root] = Tree[root << 1] * Tree[root << 1 | 1]; }

void Build(int root, int l, int r) {
  if (l == r) {
    Tree[root] = g[id[l]];
    return;
  }
  int Mid = (l + r) >> 1;
  Build(root << 1, l, Mid);
  Build(root << 1 | 1, Mid + 1, r);
  PushUp(root);
}

matrix Query(int root, int l, int r, int L, int R) {
  if (L <= l && r <= R) return Tree[root];
  int Mid = (l + r) >> 1;
  if (R <= Mid) return Query(root << 1, l, Mid, L, R);
  if (Mid < L) return Query(root << 1 | 1, Mid + 1, r, L, R);
  return Query(root << 1, l, Mid, L, R) *
         Query(root << 1 | 1, Mid + 1, r, L, R);
  // Pay attention to the writing of the query operation
}

void Modify(int root, int l, int r, int pos) {
  if (l == r) {
    Tree[root] = g[id[l]];
    return;
  }
  int Mid = (l + r) >> 1;
  if (pos <= Mid)
    Modify(root << 1, l, Mid, pos);
  else
    Modify(root << 1 | 1, Mid + 1, r, pos);
  PushUp(root);
}

void Update(int x, int val) {
  g[x].g[1][0] += val - a[x];
  a[x] = val;
  // First modify the g matrix of x
  while (x) {
    matrix last = Query(1, 1, n, p[top[x]], End[top[x]]);
    // Query the original g matrix of top[x]
    Modify(1, 1, n,
           p[x]);  // Perform the modification (the g matrix of point x has been modified but not yet updated in the segment tree)
    matrix now = Query(1, 1, n, p[top[x]], End[top[x]]);
    // Query the new g matrix of top[x]
    x = fa[top[x]];
    g[x].g[0][0] +=
        max(now.g[0][0], now.g[1][0]) - max(last.g[0][0], last.g[1][0]);
    g[x].g[0][1] = g[x].g[0][0];
    g[x].g[1][0] += now.g[0][0] - last.g[0][0];
    // Modify the g matrix of fa[top[x]] based on the change
  }
}

void add(int u, int v) {
  To[++e] = v;
  Next[e] = Begin[u];
  Begin[u] = e;
}

void DFS1(int u) {
  sz[u] = 1;
  int Max = 0;
  f[u][1] = a[u];
  for (int i = Begin[u]; i; i = Next[i]) {
    int v = To[i];
    if (v == fa[u]) continue;
    dis[v] = dis[u] + 1;
    fa[v] = u;
    DFS1(v);
    sz[u] += sz[v];
    if (sz[v] > Max) {
      Max = sz[v];
      son[u] = v;
    }
    f[u][1] += f[v][0];
    f[u][0] += max(f[v][0], f[v][1]);
    // Calculate f[i][0/1] during DFS1
  }
}

void DFS2(int u, int t) {
  top[u] = t;
  p[u] = ++cnt;
  id[cnt] = u;
  End[t] = cnt;
  g[u].g[1][0] = a[u];
  g[u].g[1][1] = -INF;
  if (!son[u]) return;
  DFS2(son[u], t);
  for (int i = Begin[u]; i; i = Next[i]) {
    int v = To[i];
    if (v == fa[u] || v == son[u]) continue;
    DFS2(v, v);
    g[u].g[0][0] += max(f[v][0], f[v][1]);
    g[u].g[1][0] += f[v][0];
    // Calculate the g matrix based on f[i][0/1]
  }
  g[u].g[0][1] = g[u].g[0][0];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n - 1; i++) {
    int u, v;
    cin >> u >> v;
    add(u, v);
    add(v, u);
  }
  dis[1] = 1;
  DFS1(1);
  DFS2(1, 1);
  Build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    int x, val;
    cin >> x >> val;
    Update(x, val);
    matrix ans = Query(1, 1, n, 1, End[1]);  // Query the matrix multiplication of the heavy chain containing node 1
    cout << max(ans.g[0][0], ans.g[1][0]) << '\n';
  }
  return 0;
}
```

Exercises

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