AIOJ

Dynamic centroid decomposition

Dynamic centroid decomposition is used to solve problems involving information about paths in a tree with vertex-weight/edge-weight updates.

Centroid tree

Let us review the computation process of centroid decomposition.

For a node $x$ , the simple paths in its subtree are of two kinds: those passing through $x$ , consisting of one or two paths starting from $x$ , and those not passing through $x$ , which are already contained in the subtrees of its children.

To compute the simple paths in a subtree, we choose a decomposition center $rt$ , compute the path information in the subtree that passes through this node, and then, for each of its children, regard the connected component containing that child after deleting $rt$ as a subtree and recurse. The selected decomposition centers form a tree structure called the centroid tree. The total size of the connected components represented by nodes at the same level of the centroid tree (that is, the components whose decomposition centers are those nodes) is $O(n)$ . This means that the time complexity of centroid decomposition depends on the depth of the centroid tree: if its depth is $h$ , the complexity is $O(nh)$ .

It can be proved that choosing the centroid of each connected component as the decomposition center minimizes the depth of the centroid tree, which is $O(\log n)$ . Thus, the resulting complexity is $O(n\log n)$ when collecting information about $O(n^2)$ paths in the tree.

Because the shape of the tree does not change during dynamic centroid decomposition, the shape of the centroid tree does not change either.

Here is reference code for constructing the centroid tree:

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] is the maximum subtree size when x is the root
  if (maxx[x] < maxx[rt])
    rt = x;  // Do not write <= here; this ensures that rt does not change during the second calcsiz call
}

void pre(int x) {
  vis[x] = true;  // Indicates that x is ignored in subsequent processing
  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 call obtains the subtree sizes when rooted at rt
      fa[rt] = x;
      pre(rt);  // Record the parent in the centroid 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 move up the centroid tree by repeatedly following parent pointers and update the values. Since the depth of the centroid tree is at most $O(\log n)$ , the complexity is bounded.

During dynamic centroid decomposition, we need information such as the distance from a node to its ancestors in the centroid tree. Since a node has at most $O(\log n)$ ancestors, we can compute the depth $dep[x]$ while constructing the centroid tree or use LCA to preprocess these distances or answer them online. Note: the distances from a node to its ancestors in the centroid tree are not necessarily increasing, so they cannot be accumulated!

During dynamic centroid decomposition, information about a node may be counted repeatedly in the records of its ancestors in the centroid tree; we need to remove the effect of these duplicates. A common method is to record information for each connected component in two ways: one is the distance to the decomposition center, and the other is the distance to the parent of the decomposition center in the centroid tree. This will be demonstrated in the example problems.

Example problem “ZJOI2007” Hide and Seek

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

Invert the color of a node (white becomes black, and black becomes white).
Query the distance between the two farthest black nodes in the tree.

$n\le 10^5,m\le 5\times 10^5$

After constructing the centroid tree, for each node $x$ maintain two heaps with deletion. $dist[x]$ stores the distances from all black nodes in the connected component represented by node $x$ to $x$ . $ch[x]$ stores the distances from black nodes in all children in the centroid tree and from $x$ itself to $x$ . Because of the greedy method used to obtain the answer in this problem, and because two paths from the same subtree cannot form a complete path, we insert into this heap only its own value and the maximum value from each subtree. The sum of the two largest values in $ch[x]$ (or all values if there are fewer than two) is the longest path between black endpoints passing through node $x$ when $x$ is the decomposition center. We can use a deletion heap $ans$ to store the answer for every node; the maximum value in this heap is the answer we seek.

We can maintain the deletion heaps $dist[x],ch[x],ans$ according to the definitions above. When a value in $dist[x]$ changes, in $O(\log n)$ time we can also maintain $ch[x],ans$ .

Now consider how the value of $dist[x]$ changes when we invert the color of a node. If the node was originally black, we perform a deletion; if it was originally white, we perform an insertion.

Suppose we invert the color of node $x$ . For every ancestor $u$ , update $dist[u]$ by inserting or deleting $dist(x,u)$ , while maintaining $ch[x],ans$ . In particular, in $ch[x]$ , insert or delete the value $0$ .

Reference code:

#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] is the maximum subtree size when x is the root
  if (maxx[x] < maxx[rt])
    rt = x;  // Do not write <= here; this ensures that rt does not change during the second calcsiz call
}

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;  // Ignore x
  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);  // Compute twice; the second call obtains the subtree sizes when rooted at rt
      fa[rt] = x;
      dfs(p[j], -1, 1, dist[rt]);
      ch[x].insert(dist[rt].top());
      dep[rt] = dep[x] + 1;
      pre(rt);  // Record the parent 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;
  int cnt = n;
  while (m--) {
    cin >> op;
    if (op == 'G') {
      if (cnt)
        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());
        }
        cnt--;
      } 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());
        }
        cnt++;
      }
      col[x] ^= 1;
    }
  }
  return 0;
}

Example problem Luogu P6329 [Template] Centroid Tree | Shock Wave

Given a tree with $n$ nodes, each node has a weight $v[x]$ . Implement the following two operations:

Query the sum of the weights of nodes whose distance from node $x$ is no greater than $y$ .
Change the vertex weight of node $x$ to $y$ , namely $v[x]=y$ .

We use a dynamically opened segment tree over weights to record distance information.

Following the idea of the previous problem, for each node we maintain a segment tree $dist[x]$ , which represents the distance information from every node in the decomposition component $x$ to node $x$ ; the index is the distance, and the stored value is increased by the vertex weight. The segment tree $ch[x]$ represents the distance information from every node in the decomposition component $x$ to the parent of $x$ in the centroid tree.

In this problem, every query and update must modify all ancestors in the centroid tree.

For example, for a query, suppose we want the sum of the weights of nodes whose distance from node $x$ is no greater than $y$ . First add to the answer the sum in the segment tree $dist[x]$ over indices from $0$ to $y$ . Then, with $x$ fixed, traverse every ancestor $u$ in the centroid tree, let its child one level below be $v$ , and set $d=dist(x,u)$ . If we exclude the subtree containing $x$ , that is, the subtree rooted at $v$ , add to the answer the sum in the segment tree $dist[u]$ over indices from $0$ to $y-d$ . Since the part rooted at $v$ has been counted twice, subtract the sum in the segment tree $ch[v]$ over indices from $0$ to $y-d$ .

When performing an update, we must maintain both $dist[x]$ and $ch[x]$ .