AIOJ

Prerequisites: Matrix, Heavy-Light Decomposition.

Dynamic DP is a piece of black magic taught by Maokun at WC2018, generally used to solve DP problems on trees with point-weight (or edge-weight) modification operations.

Example

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

Example Problem Luogu P4719【Template】Dynamic DP

Given a tree with $n$ vertices, each with a vertex weight. There are $m$ operations; each operation gives $x,y$ and changes the weight of vertex $x$ to $y$ . After each operation, you need to find the weight of the maximum-weight independent set of this 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 the $\max$ operation in ordinary matrix multiplication.

Generalized matrix multiplication is also associative, so matrix fast exponentiation can be used.

Without Modification Operations

Let $f_{i,0}$ denote the maximum answer when $i$ is not selected, and $f_{i,1}$ denote the maximum answer when $i$ is selected.

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 there is a heavy chain:

Let $g_{i,0}$ denote the maximum answer when $i$ is not selected and only the subtrees of $i$ 's light children may be selected; let $g_{i,1}$ denote the maximum answer when $i$ is selected without considering $son_i$ , where $son_i$ denotes the heavy child of $i$ .

Suppose 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})$ .

A matrix can be constructed:

\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 use the generalized multiplication rule here.

It can be seen that during a modification operation, we only need to modify $g_{i,1}$ and every heavy chain above it.

Specific Approach

Use DFS preprocessing to calculate $f_{i,0/1}$ and $g_{i,0/1}$ .
Perform heavy-light decomposition on the tree (note that because querying a vertex requires calculating the interval matrix product from that vertex to the end of the heavy chain containing it, for every vertex record $End_i$ , representing the index of the last vertex of the heavy chain containing $i$ ). Build a segment tree for each heavy chain; the segment tree maintains the $g$ matrices and interval products of the $g$ matrices.
During a modification, first modify $g_{i,1}$ and the matrix of vertex $i$ in the segment tree, calculate the change in the matrix of $top_i$ , and apply the change to the matrix of $fa_{top_i}$ .
A query is simply the interval product from 1 to the end of the heavy chain containing it, followed by taking a $\max$ .

Code Implementation

#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] is the index of i after heavy-light 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 constructed segment tree; g[] maintains the matrix of each vertex

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);
  // Note how the query operation is written
}

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 x's g matrix
  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 vertex x has been modified, but the one in the segment tree has not)
    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]] according to 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]);
    // Compute f[i][0/1] during DFS1 as well
  }
}

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];
    // Obtain the g matrix from 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 product of the heavy chain containing 1
    cout << max(ans.g[0][0], ans.g[1][0]) << '\n';
  }
  return 0;
}