Skip to content

Dynamic Tree Divide and Conquer

Dynamic Tree Divide and Conquer

Dynamic Tree Divide and Conquer is used to solve tree path information statistics problems with vertex/edge weight updates.

Centroid Decomposition Tree

Recall the computation process of centroid decomposition.

For a node \(x\), the simple paths in its subtree fall into two categories: those passing through node \(x\), consisting of one or two paths starting from \(x\); and those not passing through \(x\), which are already contained within the subtrees of all its child nodes.

To compute simple paths within a subtree, we select a decomposition center \(rt\), calculate the information of paths in the subtree passing through this node, then for each child node, treat the connected component containing that node after removing \(rt\) as a subtree and recursively compute. The selected decomposition centers can form a tree structure called the centroid decomposition tree. We observe that the total size of the connected blocks represented by nodes at the same level in the centroid decomposition tree (i.e., the connected blocks with that node as the decomposition center) is \(O(n)\). This implies that the time complexity of centroid decomposition is related to the depth of the centroid decomposition tree. If the depth of the centroid decomposition tree is \(h\), then the complexity of centroid decomposition is \(O(nh)\).

It can be proven that when we select the centroid of the connected block as the decomposition center each time, the depth of the centroid decomposition tree is minimized, at \(O(\log n)\). Thus, we can statistically process information for \(O(n^2)\) paths on the tree within \(O(n\log n)\) time complexity.

Since the tree structure does not change during dynamic centroid decomposition, the structure of the centroid decomposition tree also remains unchanged.

Below is reference code for constructing the centroid decomposition tree:

 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
void calcsiz(int x, int f) {
  siz[x] = 1;
  maxx[x] = 0;
  for (int j = h[x]; j; j = nxt[j])
    if (p[j] != f && !vis[p[j]]) {
      calcsiz(p[j], x);
      siz[x] += siz[p[j]];
      maxx[x] = max(maxx[x], siz[p[j]]);
    }
  maxx[x] =
      max(maxx[x], sum - siz[x]);  // maxx[x] represents the maximum subtree size when x is the root
  if (maxx[x] < maxx[rt])
    rt = x;  // Cannot use <= here, ensuring rt does not change during the second calcsiz
}

void pre(int x) {
  vis[x] = true;  // Indicates that node x will not be considered in subsequent processes
  for (int j = h[x]; j; j = nxt[j])
    if (!vis[p[j]]) {
      sum = siz[p[j]];
      rt = 0;
      maxx[rt] = inf;
      calcsiz(p[j], -1);
      calcsiz(rt, -1);  // Compute twice; the second time calculates subtree sizes with rt as root
      fa[rt] = x;
      pre(rt);  // Record the father in the centroid decomposition tree
    }
}

int main() {
  sum = n;
  rt = 0;
  maxx[rt] = inf;
  calcsiz(1, -1);
  calcsiz(rt, -1);
  pre(rt);
}

Implementing Updates

During queries and updates, we traverse up the centroid decomposition tree by jumping to ancestors and updating. Since the depth of the centroid decomposition tree is at most \(O(\log n)\), this ensures acceptable complexity.

During dynamic centroid decomposition, we need information such as the distance from a node to its ancestors in the centroid decomposition tree. Since a node has at most \(O(\log n)\) ancestors, we can precompute the depth \(dep[x]\) or use LCA while constructing the centroid decomposition tree to preprocess these distances or implement real-time queries. Note: The distance from a node to its ancestors in the centroid decomposition tree is not necessarily monotonic; it cannot be accumulated!

During dynamic centroid decomposition, a node's information might be counted multiple times in its ancestors' information in the centroid decomposition tree. We need to eliminate the effect of these duplicates. A common method is to record information for a connected block in two ways: one is its distance information to the decomposition center, and the other is its distance information to the father of the decomposition center in the centroid decomposition tree. This part will be demonstrated in the example problems.

Example 「ZJOI2007」Hide and Seek

Given a tree with \(n\) nodes, initially all nodes are black. Implement the following two operations:

  1. Toggle the color of a node (white to black, black to white);

  2. Query the distance between the two farthest black nodes on the tree.

    \(n\le 10^5,m\le 5\times 10^5\)

Construct the centroid decomposition tree. For each node \(x\), maintain two erasable heaps. \(dist[x]\) stores distance information from all black nodes in the connected block represented by \(x\) to \(x\). \(ch[x]\) stores distance information from all black nodes among \(x\)'s children in the centroid decomposition tree and itself to \(x\). Due to the greedy method for answering queries in this problem, and since two paths from the same subtree cannot form a complete path, we only insert its own value and the maximum value from each of its subtrees into this heap. We find that the sum of the two largest values in \(ch[x]\) (or all values if there are less than two) is the longest black endpoint path passing through node \(x\) when the decomposition center is \(x\). We can use an erasable heap \(ans\) to store the answers for all nodes; the maximum value in this heap is the desired answer.

We can maintain these erasable heaps \(dist[x], ch[x], ans\) according to the definitions above. When values in \(dist[x]\) change, we can also maintain \(ch[x]\) and \(ans\) in \(O(\log n)\) time complexity.

Now let's see how \(dist[x]\) changes when we toggle a node's color. When the node was originally black, we perform a deletion operation; when it was originally white, we perform an insertion operation.

Suppose we want to toggle the color of node \(x\). For all its ancestors \(u\), we insert or delete \(dist(x,u)\) in \(dist[u]\), and simultaneously maintain the values of \(ch[x]\) and \(ans\). Specifically, we need to insert or delete the value \(0\) in \(ch[x]\).

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
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
```cpp
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
constexpr int MAXN = 100010;
constexpr int inf = 2e9;
int n, a, b, m, x, col[MAXN];
// 0 off 1 on
char op;
int cur, h[MAXN * 2], nxt[MAXN * 2], p[MAXN * 2];

void add_edge(int x, int y) {
  cur++;
  nxt[cur] = h[x];
  h[x] = cur;
  p[cur] = y;
}

bool vis[MAXN];
int rt, sum, siz[MAXN], maxx[MAXN], fa[MAXN], dep[MAXN];

void calcsiz(int x, int f) {
  siz[x] = 1;
  maxx[x] = 0;
  for (int j = h[x]; j; j = nxt[j])
    if (p[j] != f && !vis[p[j]]) {
      calcsiz(p[j], x);
      siz[x] += siz[p[j]];
      maxx[x] = max(maxx[x], siz[p[j]]);
    }
  maxx[x] =
      max(maxx[x], sum - siz[x]);  // maxx[x] represents the maximum subtree size when x is the root
  if (maxx[x] < maxx[rt])
    rt = x;  // Cannot use <= here, ensures rt does not change during the second calcsiz
}

struct heap {
  priority_queue<int> A, B;  // heap = A - B

  void insert(int x) { A.push(x); }

  void erase(int x) { B.push(x); }

  int top() {
    while (!B.empty() && A.top() == B.top()) A.pop(), B.pop();
    return A.top();
  }

  void pop() {
    while (!B.empty() && A.top() == B.top()) A.pop(), B.pop();
    A.pop();
  }

  int top2() {
    int t = top(), ret;
    pop();
    ret = top();
    A.push(t);
    return ret;
  }

  int size() { return A.size() - B.size(); }
} dist[MAXN], ch[MAXN], ans;

void dfs(int x, int f, int d, heap& y) {
  y.insert(d);
  for (int j = h[x]; j; j = nxt[j])
    if (p[j] != f && !vis[p[j]]) dfs(p[j], x, d + 1, y);
}

void pre(int x) {
  vis[x] = true;  // Exclude x from consideration
  for (int j = h[x]; j; j = nxt[j])
    if (!vis[p[j]]) {
      rt = 0;
      maxx[rt] = inf;
      sum = siz[p[j]];
      calcsiz(p[j], -1);
      calcsiz(rt, -1);  // Calculate twice, the second time to get subtree sizes with rt as root
      fa[rt] = x;
      dfs(p[j], -1, 1, dist[rt]);
      ch[x].insert(dist[rt].top());
      dep[rt] = dep[x] + 1;
      pre(rt);  // Record father in the centroid tree
    }
  ch[x].insert(0);
  if (ch[x].size() >= 2)
    ans.insert(ch[x].top() + ch[x].top2());
  else if (ch[x].size())
    ans.insert(ch[x].top());
}

struct LCA {
  int dep[MAXN], lg[MAXN], fa[MAXN][20];

  void dfs(int x, int f) {
    for (int j = h[x]; j; j = nxt[j])
      if (p[j] != f) dep[p[j]] = dep[x] + 1, fa[p[j]][0] = x, dfs(p[j], x);
  }

  void init() {
    dfs(1, -1);
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    for (int j = 1; j <= lg[n]; j++)
      for (int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1];
  }

  int query(int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    int k = dep[y] - dep[x];
    for (int i = 0; k; k = k / 2, i++)
      if (k & 1) y = fa[y][i];
    if (x == y) return x;
    k = dep[x];
    for (int i = lg[k]; i >= 0; i--)
      if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
  }

  int dist(int x, int y) { return dep[x] + dep[y] - 2 * dep[query(x, y)]; }
} lca;

int d[MAXN][20];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i < n; i++) cin >> a >> b, add_edge(a, b), add_edge(b, a);
  lca.init();
  rt = 0;
  maxx[rt] = inf;
  sum = n;
  calcsiz(1, -1);
  calcsiz(rt, -1);
  pre(rt);
  for (int i = 1; i <= n; i++)
    for (int j = i; j; j = fa[j]) d[i][dep[i] - dep[j]] = lca.dist(i, j);
  cin >> m;
  while (m--) {
    cin >> op;
    if (op == 'G') {
      if (ans.size())
        cout << ans.top() << '\n';
      else
        cout << "-1\n";
    } else {
      cin >> x;
      if (!col[x]) {
        if (ch[x].size() >= 2) ans.erase(ch[x].top() + ch[x].top2());
        ch[x].erase(0);
        if (ch[x].size() >= 2) ans.insert(ch[x].top() + ch[x].top2());
        for (int i = x; fa[i]; i = fa[i]) {
          if (ch[fa[i]].size() >= 2)
            ans.erase(ch[fa[i]].top() + ch[fa[i]].top2());
          ch[fa[i]].erase(dist[i].top());
          dist[i].erase(d[x][dep[x] - dep[fa[i]]]);
          if (dist[i].size()) ch[fa[i]].insert(dist[i].top());
          if (ch[fa[i]].size() >= 2)
            ans.insert(ch[fa[i]].top() + ch[fa[i]].top2());
        }
      } else {
        if (ch[x].size() >= 2) ans.erase(ch[x].top() + ch[x].top2());
        ch[x].insert(0);
        if (ch[x].size() >= 2) ans.insert(ch[x].top() + ch[x].top2());
        for (int i = x; fa[i]; i = fa[i]) {
          if (ch[fa[i]].size() >= 2)
            ans.erase(ch[fa[i]].top() + ch[fa[i]].top2());
          if (dist[i].size()) ch[fa[i]].erase(dist[i].top());
          dist[i].insert(d[x][dep[x] - dep[fa[i]]]);
          ch[fa[i]].insert(dist[i].top());
          if (ch[fa[i]].size() >= 2)
            ans.insert(ch[fa[i]].top() + ch[fa[i]].top2());
        }
      }
      col[x] ^= 1;
    }
  }
  return 0;
}

  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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
???+ note "Example [Luogu P6329【Template】Centroid Decomposition Tree | Shockwave](https://www.luogu.com.cn/problem/P6329)"
    Given a tree with $n$ nodes, each node has a weight $v[x]$. Implement the following two operations:

    1.  Query the sum of weights of nodes whose distance to node $x$ does not exceed $y$;
    2.  Modify the weight of node $x$ to $y$, i.e., $v[x]=y$.

We use dynamically allocated weight segment trees to record distance information.

Similar to the previous problem's approach, for each node, we maintain a segment tree $dist[x]$, representing the distance information from all nodes in decomposition block $x$ to node $x$, with distance as index and adding node weights as values. The segment tree $ch[x]$ represents the distance information from all nodes in decomposition block $x$ to the father node of $x$ in the centroid decomposition tree.

In this problem, all queries and modifications need to be applied to all ancestors in the centroid decomposition tree.

Taking the query operation as an example, if we want to query the sum of weights of nodes whose distance to node $x$ does not exceed $y$, we first add the sum of values from index $0$ to $y$ in segment tree $dist[x]$ to the answer. Then we traverse all ancestors $u$ of $x$, let the lower-level ancestor be $v$, and set $d=dist(x,u)$. If we do not enter the subtree containing $x$, i.e., the subtree rooted at $v$, then we add the sum of values from index $0$ to $y-d$ in segment tree $dist[u]$ to the answer. Since we have double-counted the part rooted at $v$, we subtract the sum of values from index $0$ to $y-d$ in segment tree $ch[v]$ from the answer.

During modification operations, we need to maintain both $dist[x]$ and $ch[x]$.

Reference code:

```cpp
```cpp
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int MAXN = 100010;
constexpr int inf = 2e9;
constexpr int ddd = 6000010;

struct Segtree {
  int cnt, rt[MAXN], sum[ddd], lc[ddd], rc[ddd];

  void update(int& o, int l, int r, int x, int v) {
    if (!o) o = ++cnt;
    if (l == r) {
      sum[o] += v;
      return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
      update(lc[o], l, mid, x, v);
    else
      update(rc[o], mid + 1, r, x, v);
    sum[o] = sum[lc[o]] + sum[rc[o]];
  }

  int query(int o, int l, int r, int ql, int qr) {
    if (!o || r < ql || l > qr) return 0;
    if (ql <= l && r <= qr) return sum[o];
    int mid = (l + r) >> 1;
    return query(lc[o], l, mid, ql, qr) + query(rc[o], mid + 1, r, ql, qr);
  }
} dist, ch;

int n, m, val[MAXN], u, v, op, x, y, lstans;
int cur, h[MAXN * 2], nxt[MAXN * 2], p[MAXN * 2];

void add_edge(int x, int y) {
  cur++;
  nxt[cur] = h[x];
  h[x] = cur;
  p[cur] = y;
}

struct LCA {
  int dep[MAXN], lg[MAXN], fa[MAXN][20];

  void dfs(int x, int f) {
    for (int j = h[x]; j; j = nxt[j])
      if (p[j] != f) dep[p[j]] = dep[x] + 1, fa[p[j]][0] = x, dfs(p[j], x);
  }

  void init() {
    dep[1] = 1;
    dfs(1, -1);
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    for (int j = 1; j <= lg[n]; j++)
      for (int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1];
  }

  int query(int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    int k = dep[y] - dep[x];
    for (int i = 0; k; k = k / 2, i++)
      if (k & 1) y = fa[y][i];
    if (x == y) return x;
    k = dep[x];
    for (int i = lg[k]; i >= 0; i--)
      if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
  }

  int dist(int x, int y) { return dep[x] + dep[y] - 2 * dep[query(x, y)]; }
} lca;

int rt, sum, siz[MAXN], maxx[MAXN], fa[MAXN];
int d[MAXN][20], dep[MAXN];
bool vis[MAXN];

void calcsiz(int x, int fa) {
  siz[x] = 1;
  maxx[x] = 0;
  for (int j = h[x]; j; j = nxt[j])
    if (p[j] != fa && !vis[p[j]]) {
      calcsiz(p[j], x);
      siz[x] += siz[p[j]];
      maxx[x] = max(maxx[x], siz[p[j]]);
    }
  maxx[x] =
      max(maxx[x], sum - siz[x]);  // maxx[x] represents the maximum subtree size when x is the root
  if (maxx[x] < maxx[rt])
    rt = x;  // Cannot use <= here, ensures rt does not change during the second calcsiz
}

void dfs1(int x, int fa, int y, int d) {
  ch.update(ch.rt[y], 0, n, d, val[x]);
  for (int j = h[x]; j; j = nxt[j])
    if (p[j] != fa && !vis[p[j]]) dfs1(p[j], x, y, d + 1);
}

void dfs2(int x, int fa, int y, int d) {
  dist.update(dist.rt[y], 0, n, d, val[x]);
  for (int j = h[x]; j; j = nxt[j])
    if (p[j] != fa && !vis[p[j]]) dfs2(p[j], x, y, d + 1);
}

void pre(int x) {
  vis[x] = true;  // Indicates that point x will not be considered in subsequent processes
  dfs2(x, -1, x, 0);
  for (int j = h[x]; j; j = nxt[j])
    if (!vis[p[j]]) {
      rt = 0;
      maxx[rt] = inf;
      sum = siz[p[j]];
      calcsiz(p[j], -1);
      calcsiz(rt, -1);  // Calculate twice, the second time to get subtree sizes with rt as root
      dfs1(p[j], -1, rt, 1);
      fa[rt] = x;
      dep[rt] = dep[x] + 1;
      pre(rt);  // Record the father in the centroid tree
    }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> val[i];
  for (int i = 1; i < n; i++) cin >> u >> v, add_edge(u, v), add_edge(v, u);
  lca.init();
  rt = 0;
  maxx[rt] = inf;
  sum = n;
  calcsiz(1, -1);
  calcsiz(rt, -1);
  pre(rt);
  for (int i = 1; i <= n; i++)
    for (int j = i; j; j = fa[j]) d[i][dep[i] - dep[j]] = lca.dist(i, j);
  while (m--) {
    cin >> op >> x >> y;
    x ^= lstans;
    y ^= lstans;
    if (op == 0) {
      lstans = dist.query(dist.rt[x], 0, n, 0, y);
      int nww = 0;
      for (int i = x; fa[i]; i = fa[i]) {
        nww = d[x][dep[x] - dep[fa[i]]];  // lca.dist(x,fa[i]);
        lstans += dist.query(dist.rt[fa[i]], 0, n, 0, y - nww);
        lstans -= ch.query(ch.rt[i], 0, n, 0, y - nww);
      }
      cout << lstans << '\n';
    }
    if (op == 1) {
      int nww = 0;
      dist.update(dist.rt[x], 0, n, 0, y - val[x]);
      for (int i = x; fa[i]; i = fa[i]) {
        nww = d[x][dep[x] - dep[fa[i]]];  // lca.dist(x,fa[i]);
        dist.update(dist.rt[fa[i]], 0, n, nww, y - val[x]);
        ch.update(ch.rt[i], 0, n, nww, y - val[x]);
      }
      val[x] = y;
    }
  }
  return 0;
}
```

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