Skip to content

Mo's Algorithm on Trees

Mo's algorithm on the bracket sequence

Ordinary Mo's algorithm only handles problems on a sequence, so we have to flatten the tree into one by force.

Take the bracket sequence of the tree, divide it into blocks, and run Mo's algorithm on it.

How exactly?

Procedure

Maintain the bracket sequence of the tree with a DFS: append \(x\) to the sequence on entering node \(x\), and append it again on leaving. The sequence has total length \(2N\).

Let \(st_x\) be the time at which \(x\) is entered and \(ed_x\) the time at which it is left.

By the properties of the bracket sequence, for a path \(u \to v\) in the tree (assume without loss of generality that \(st_u \le st_v\)):

  • If \(\text{LCA}(u, v) = u\), every node on the path occurs exactly once in the range \([st_u, st_v]\), and every node off the path occurs 0 or 2 times.
  • If \(\text{LCA}(u, v) \neq u\), every node on the path except \(\text{LCA}(u, v)\) occurs exactly once in the range \([ed_u, st_v]\), and every node off the path occurs 0 or 2 times. Handle \(\text{LCA}(u, v)\) separately: it occurs 0 times.

So while Mo's algorithm runs, it makes no difference whether the element a pointer passes records a node being pushed or popped: either way, the number of times that node occurs in the current range changes. We only need to maintain how many times each node \(x\) occurs. A node that occurs 0 or 2 times is not in the set of path nodes we maintain, and a node that occurs once is. So when the pointers of Mo's algorithm rest at \([st_u, st_v]\), the set is almost exactly the set of nodes on the path \(u \to v\).

In practice, maintain the number of occurrences of each node \(x\) modulo 2, which tells whether the node is present. Moving a pointer, whether it adds or deletes an element, then just flips the state of that node.

Note that for a query with \(\text{LCA} \neq u\), once the pointers are in place we have to add \(\text{LCA}(u, v)\) to the set temporarily by hand (flip its state), compute and record the answer to the query, and then remove \(\text{LCA}(u, v)\) from the set again (flip it once more), so that later pointer moves are not disturbed.

Example problems

Example: [WC2013] Candy Park

Problem statement: you are given a tree in which node \(i\) has color \(c_i\). Each query gives a path \(u_i\), \(v_i\) and asks for the value, over that path, of

\(\sum_{c}val_c\sum_{i=1}^{cnt_c}w_i\)

where \(val\) is the value of a color, \(cnt\) is the number of times the color occurs, and \(w\) is the value of the color once it has occurred \(i\) times.

Procedure

First turn the tree into a sequence. Each time a node is added, its contribution to the answer can be found in \(O(1)\): it is \(val_c\times w_{cnt_c+1}\).

But the range also sweeps the whole subtree of the starting point, which produces extra contributions. What can we do about that?

During the sweep, every node in the subtree of the starting point is swept twice, yet it should contribute 0.

So keep an array \(vis\), and every time node x is swept, XOR \(vis_x\) with 1.

If \(vis_x=0\), the contribution of this node is not counted.

The problem can therefore be solved with Mo's algorithm on trees.

To handle updates, just add a time dimension; this gives Mo's algorithm on trees with updates.

Finally, the range may not contain the LCA. When it does not, add the missing contribution, and we are done.

Implementation

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
 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
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

constexpr int MAXN = 200010;

int f[MAXN], g[MAXN], id[MAXN], head[MAXN], cnt, last[MAXN], dep[MAXN],
    fa[MAXN][22], v[MAXN], w[MAXN];
int block, index, n, m, q;
int pos[MAXN], col[MAXN], app[MAXN];
bool vis[MAXN];
long long ans[MAXN], cur;

struct edge {
  int to, nxt;
} e[MAXN];

int cnt1 = 0, cnt2 = 0;  // timestamps

struct query {
  int l, r, t, id;

  bool operator<(const query &b) const {
    return (pos[l] < pos[b.l]) || (pos[l] == pos[b.l] && pos[r] < pos[b.r]) ||
           (pos[l] == pos[b.l] && pos[r] == pos[b.r] && t < b.t);
  }
} a[MAXN], b[MAXN];

void addedge(int x, int y) {
  e[++cnt] = edge{y, head[x]};
  head[x] = cnt;
}

void dfs(int x) {
  id[f[x] = ++index] = x;
  for (int i = head[x]; i; i = e[i].nxt) {
    if (e[i].to != fa[x][0]) {
      fa[e[i].to][0] = x;
      dep[e[i].to] = dep[x] + 1;
      dfs(e[i].to);
    }
  }
  id[g[x] = ++index] = x;  // bracket sequence
}

int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  if (dep[x] != dep[y]) {  // climb to the same height
    int dis = dep[x] - dep[y];
    for (int i = 20; i >= 0; i--)
      if (dis >= (1 << i)) dis -= 1 << i, x = fa[x][i];
  }
  if (x == y) return x;
  for (int i = 20; i >= 0; i--) {
    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
  }
  return fa[x][0];
}

void add(int x) {
  if (vis[x])
    cur -= (long long)v[col[x]] * w[app[col[x]]--];
  else
    cur += (long long)v[col[x]] * w[++app[col[x]]];
  vis[x] ^= 1;
}

// move along the time dimension
void modify(int x, int t) {
  if (vis[x]) {
    add(x);
    col[x] = t;
    add(x);
  } else
    col[x] = t;
}

int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= m; i++) scanf("%d", &v[i]);
  for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    addedge(x, y);
    addedge(y, x);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &last[i]);
    col[i] = last[i];
  }
  dfs(1);
  for (int j = 1; j <= 20; j++)
    for (int i = 1; i <= n; i++)
      fa[i][j] = fa[fa[i][j - 1]][j - 1];  // precompute the ancestors
  int block = pow(index, 2.0 / 3);
  for (int i = 1; i <= index; i++) {
    pos[i] = (i - 1) / block;
  }
  while (q--) {
    int opt, x, y;
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 0) {
      b[++cnt2].l = x;
      b[cnt2].r = last[x];
      last[x] = b[cnt2].t = y;
    } else {
      if (f[x] > f[y]) swap(x, y);
      a[++cnt1] = query{lca(x, y) == x ? f[x] : g[x], f[y], cnt2, cnt1};
    }
  }
  sort(a + 1, a + cnt1 + 1);
  int L, R, T;  // pointer positions
  L = R = 0;
  T = 1;
  for (int i = 1; i <= cnt1; i++) {
    while (T <= a[i].t) {
      modify(b[T].l, b[T].t);
      T++;
    }
    while (T > a[i].t) {
      modify(b[T].l, b[T].r);
      T--;
    }
    while (L > a[i].l) {
      L--;
      add(id[L]);
    }
    while (L < a[i].l) {
      add(id[L]);
      L++;
    }
    while (R > a[i].r) {
      add(id[R]);
      R--;
    }
    while (R < a[i].r) {
      R++;
      add(id[R]);
    }
    int x = id[L], y = id[R];
    int llca = lca(x, y);
    if (x != llca && y != llca) {
      add(llca);
      ans[a[i].id] = cur;
      add(llca);
    } else
      ans[a[i].id] = cur;
  }
  for (int i = 1; i <= cnt1; i++) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}

True Mo's algorithm on trees

The method above merely turns the tree into a path. What follows is the real Mo's algorithm on trees.

Problems on Mo's algorithm are all template problems, so we do not explain the implementation in much detail.

Sorting the queries

Mo's algorithm is built on sqrt decomposition, so to guarantee the time complexity we need a way to divide a tree into blocks.

The conditions:

  • Two nodes of the same block are no farther apart than the given block size.
  • A block has neither too many nodes nor too few.
  • Every node belongs to a block.
  • Blocks with adjacent indices are not too far apart.

With these conditions in mind, look at the problem [SCOI2005] Royal Federation.

Starting from that problem, we only have to guarantee the last condition, and the question of how to form the blocks is settled.

Approach

Let lim be the desired block size. Run a DFS over the whole tree, and whenever the size of a subtree exceeds lim, put its nodes into one block. Some nodes may be left over at the root, so put those into the last block.

The method: maintain a stack as the current node, acting as the parent, visits its children. When the distance from the top of the stack to the parent exceeds the desired block size, pop those elements and make them one block. Whatever is left at the end forms a block of its own.

The final sort order: if the timestamp of the first endpoint is greater than that of the second, swap them; then sort with the block of the first endpoint as the first key and the timestamp of the second endpoint as the second key.

Moving the pointers

Procedure

A natural idea is to mark the nodes that are counted in the answer, let each pointer move straight to its target, and negate every node on the way.

But this has a problem. Suppose both pointers start at x, so x is marked. When the two pointers move to the same child (and in many other cases), x should end up unmarked, yet it stays marked: each pointer marks it once, and the two cancel out.

How do we fix this?

One property is obvious: such nodes are always LCAs, because only at an LCA can a mark be undone twice, which makes the undo fail.

So we never mark the LCA while moving. When a query needs its answer, we mark the LCA, and afterwards undo the mark.

Implementation

1
2
3
4
5
6
7
// negate all nodes on the path except the LCA
void move(int x, int y) {
  if (dp[x] < dp[y]) swap(x, y);
  while (dp[x] > dp[y]) update(x), x = fa[x];
  while (x != y) update(x), update(y), x = fa[x], y = fa[y];
  // x!=y guarantees that the LCA is not negated
}

To find the LCA we can use heavy-light decomposition. The block decomposition then fits into the first DFS of the heavy-light decomposition, and the DFS order of the second DFS can be used directly as the timestamps.

 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
int bl[100002], bls = 0;  // block of each node, number of blocks
unsigned step;            // block size
int fa[100002], dp[100002], hs[100002] = {0}, sz[100002] = {0};
// parent, depth, heavy child, size
stack<int> sta;

void dfs1(int x) {
  sz[x] = 1;
  unsigned ss = sta.size();
  for (int i = head[x]; i; i = nxt[i])
    if (ver[i] != fa[x]) {
      fa[ver[i]] = x;
      dp[ver[i]] = dp[x] + 1;
      dfs1(ver[i]);
      sz[x] += sz[ver[i]];
      if (sz[ver[i]] > sz[hs[x]]) hs[x] = ver[i];
      if (sta.size() - ss >= step) {
        bls++;
        while (sta.size() != ss) bl[sta.top()] = bls, sta.pop();
      }
    }
  sta.push(x);
}

// main
if (!sta.empty()) {
  bls++;  // this line is optional
  while (!sta.empty()) bl[sta.top()] = bls, sta.pop();
}

Time complexity

This is the important part, because it decides the block size.

Let the block size be \(unit\):

  • The x pointer: the nodes of a block are about \(unit\) apart, so within each block the x pointer moves \(unit^2\) times (\(unit\times dis_{\max}\)), for a total of \(n\times unit\) moves (\(unit^2 \times (\frac{n}{unit})\)).
  • The y pointer: within each block it moves at most \(O(n)\) times, for a total of \(\frac{n^2}{unit}\) moves (\(n \times (\frac{n}{unit})\)).

The sum is smallest at about the square root (the blocks of Mo's algorithm on trees do not have a fixed size, so there is no need to follow this strictly).

Example: [WC2013] Candy Park

Because of the extra time dimension, a block size of around \(n^{0.6}\) is good enough.

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
 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
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <stack>
using namespace std;

int gi() {
  int x, c, op = 1;
  while (c = getchar(), c < '0' || c > '9')
    if (c == '-') op = -op;
  x = c ^ 48;
  while (c = getchar(), c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48);
  return x * op;
}

int head[100002], nxt[200004], ver[200004], tot = 0;

void add(int x, int y) {
  ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
  ver[++tot] = x, nxt[tot] = head[y], head[y] = tot;
}

int bl[100002], bls = 0;
unsigned step;
int fa[100002], dp[100002], hs[100002] = {0}, sz[100002] = {0}, top[100002],
                            id[100002];
stack<int> sta;

void dfs1(int x) {
  sz[x] = 1;
  unsigned ss = sta.size();
  for (int i = head[x]; i; i = nxt[i])
    if (ver[i] != fa[x]) {
      fa[ver[i]] = x, dp[ver[i]] = dp[x] + 1;
      dfs1(ver[i]);
      sz[x] += sz[ver[i]];
      if (sz[ver[i]] > sz[hs[x]]) hs[x] = ver[i];
      if (sta.size() - ss >= step) {
        bls++;
        while (sta.size() != ss) bl[sta.top()] = bls, sta.pop();
      }
    }
  sta.push(x);
}

int cnt = 0;

void dfs2(int x, int hf) {
  top[x] = hf, id[x] = ++cnt;
  if (!hs[x]) return;
  dfs2(hs[x], hf);
  for (int i = head[x]; i; i = nxt[i])
    if (ver[i] != fa[x] && ver[i] != hs[x]) dfs2(ver[i], ver[i]);
}

int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dp[top[x]] < dp[top[y]]) swap(x, y);
    x = fa[top[x]];
  }
  return dp[x] < dp[y] ? x : y;
}

struct qu {
  int x, y, t, id;

  bool operator<(const qu a) const {
    return bl[x] == bl[a.x] ? (bl[y] == bl[a.y] ? t < a.t : bl[y] < bl[a.y])
                            : bl[x] < bl[a.x];
  }
} q[100001];

int qs = 0;

struct ch {
  int x, y, b;
} upd[100001];

int ups = 0;
long long ans[100001];
int b[100001] = {0};
int a[100001];
long long w[100001];
long long v[100001];
long long now = 0;
bool vis[100001] = {false};

void back(int t) {
  if (vis[upd[t].x]) {
    now -= w[b[upd[t].y]--] * v[upd[t].y];
    now += w[++b[upd[t].b]] * v[upd[t].b];
  }
  a[upd[t].x] = upd[t].b;
}

void change(int t) {
  if (vis[upd[t].x]) {
    now -= w[b[upd[t].b]--] * v[upd[t].b];
    now += w[++b[upd[t].y]] * v[upd[t].y];
  }
  a[upd[t].x] = upd[t].y;
}

void update(int x) {
  if (vis[x])
    now -= w[b[a[x]]--] * v[a[x]];
  else
    now += w[++b[a[x]]] * v[a[x]];
  vis[x] ^= 1;
}

void move(int x, int y) {
  if (dp[x] < dp[y]) swap(x, y);
  while (dp[x] > dp[y]) update(x), x = fa[x];
  while (x != y) update(x), update(y), x = fa[x], y = fa[y];
}

int main() {
  int n = gi(), m = gi(), k = gi();
  step = (int)pow(n, 0.6);
  for (int i = 1; i <= m; i++) v[i] = gi();
  for (int i = 1; i <= n; i++) w[i] = gi();
  for (int i = 1; i < n; i++) add(gi(), gi());
  for (int i = 1; i <= n; i++) a[i] = gi();
  for (int i = 1; i <= k; i++)
    if (gi())
      q[++qs].x = gi(), q[qs].y = gi(), q[qs].t = ups, q[qs].id = qs;
    else
      upd[++ups].x = gi(), upd[ups].y = gi();
  for (int i = 1; i <= ups; i++) upd[i].b = a[upd[i].x], a[upd[i].x] = upd[i].y;
  for (int i = ups; i; i--) back(i);
  fa[1] = 1;
  dfs1(1), dfs2(1, 1);
  if (!sta.empty()) {
    bls++;
    while (!sta.empty()) bl[sta.top()] = bls, sta.pop();
  }
  for (int i = 1; i <= n; i++)
    if (id[q[i].x] > id[q[i].y]) swap(q[i].x, q[i].y);
  sort(q + 1, q + qs + 1);
  int x = 1, y = 1, t = 0;
  for (int i = 1; i <= qs; i++) {
    if (x != q[i].x) move(x, q[i].x), x = q[i].x;
    if (y != q[i].y) move(y, q[i].y), y = q[i].y;
    int f = lca(x, y);
    update(f);
    while (t < q[i].t) change(++t);
    while (t > q[i].t) back(t--);
    ans[q[i].id] = now;
    update(f);
  }
  for (int i = 1; i <= qs; i++) printf("%lld\n", ans[i]);
  return 0;
}