Skip to content

Divide and Conquer on Trees

Centroid decomposition

Centroid decomposition works well for problems about paths in large trees.

Example 1: Luogu P3806 [Template] Centroid Decomposition 1

Given a tree with \(n\) nodes and edge weights, answer \(m\) queries. Each query gives \(k\) and asks whether the tree contains a pair of nodes at distance \(k\).

\(n\le 10000,m\le 100,k\le 10000000\)

Pick an arbitrary node \(\mathit{rt}\) as the root. The paths that lie entirely inside its subtree are of two kinds: those that pass through the current root and those that do not. The paths through the root are again of two kinds: those that have the root as an endpoint, and those whose endpoints are both different from the root. A path of the second kind can be obtained by combining two paths of the first kind. So for each root \(rt\) that we enumerate, we first compute the contribution to the answer of the paths in its subtree that pass through it, and then recurse into its child subtrees to handle the paths that do not.

In this problem, we handle the paths through the root \(\mathit{rt}\) as follows. Enumerate the children \(\mathit{ch}\) of the root and, with \(\mathit{ch}\) as the root of its subtree, compute the distance from every node in the subtree of \(\mathit{ch}\) to \(\mathit{rt}\). Let \(\mathit{dist}_i\) be the distance from node \(i\) to the current root \(rt\), and let \(\mathit{tf}_{d}\) say whether one of the subtrees processed so far contains a node \(v\) with \(\mathit{dist}_v=d\). If the \(k\) of a query satisfies \(tf_{k-\mathit{dist}_i}=true\), then a path of length \(k\) exists. Once we have checked whether the paths into the subtree of \(\mathit{ch}\) give an answer, we add the new distances to the array \(\mathit{tf}\).

Do not clear the array \(\mathit{tf}\) with memset. Instead, put every position of \(\mathit{tf}\) that has been used into a queue and clear exactly those positions; otherwise the time bound is lost.

In centroid decomposition, all the recursive calls on one level together process each node once. If the recursion has \(h\) levels, the total running time is \(O(hn)\).

If we always choose the centroid of the subtree as the root, the recursion has the fewest levels and the running time is \(O(n\log n)\). This choice is what gives the technique its name, centroid decomposition of a tree.

After choosing a new root, always recompute the subtree sizes. Otherwise a change that looks tiny can make the time complexity wrong or the correctness hard to guarantee.

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
/* size: subtree sizes d[], size of the connected component cnt
   dp: largest subtree f[], tree centroid rot
   get: distances from the nodes to the centroid, t[], top
   calc: centroid decomposition; bu[]: buckets indexed by length
   hd to nx wg: the graph, stored as a forward star
   ak[] as[]: the queries, answered offline
   ok[]: nodes already used as a centroid in the decomposition
 */
#include <iostream>
const int N = 1e4 + 4, M = 105, Q = 1e7 + 7;
int n, m, hd[N], to[N * 2], nx[N * 2], wg[N * 2];
int ak[M], d[N], f[N], t[N], top, cnt, rot;
bool as[M], ok[N], bu[Q];

int size(int u, int pa) {
  cnt++, d[u] = 1;
  for (int p = hd[u]; ~p; p = nx[p])
    if (to[p] != pa && !ok[to[p]]) d[u] += size(to[p], u);
  return d[u];
}

void dp(int u, int pa) {
  f[u] = cnt - d[u];
  for (int p = hd[u]; ~p; p = nx[p])
    if (to[p] != pa && !ok[to[p]]) {
      f[u] = std::max(f[u], d[to[p]]);
      dp(to[p], u);
    }
  if (f[u] < f[rot]) rot = u;
}

void get(int u, int pa, int dis) {
  t[top++] = dis;
  for (int p = hd[u]; ~p; p = nx[p])
    if (to[p] != pa && !ok[to[p]]) get(to[p], u, dis + wg[p]);
}

void calc(int u) {
  cnt = 0, size(u, u);
  rot = u, dp(u, u);
  bu[0] = true, t[0] = 0, top = 1;
  for (int p = hd[rot], i; ~p; p = nx[p])
    if (!ok[to[p]]) {
      i = top, get(to[p], rot, wg[p]);
      for (int q = 0; q < m; q++)
        for (int j = i; j < top && !as[q]; j++)
          if (ak[q] >= t[j]) as[q] = bu[ak[q] - t[j]];
      --i;
      while (++i < top)
        if (t[i] < Q) bu[t[i]] = true;
    }
  while (top--)
    if (t[top] < Q) bu[t[top]] = false;
  ok[rot] = true;
  for (int p = hd[rot]; ~p; p = nx[p])
    if (!ok[to[p]]) calc(to[p]);
}

int main() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; i++) hd[i] = -1;
  for (int i = 0, u, v; i + 2 < n * 2;) {
    std::cin >> u >> v >> wg[i];
    wg[i + 1] = wg[i];
    to[i] = v, nx[i] = hd[u], hd[u] = i++;
    to[i] = u, nx[i] = hd[v], hd[v] = i++;
  }
  for (int i = 0; i < m; i++) std::cin >> ak[i];
  calc(1);
  for (int i = 0; i < m; i++) std::cout << (as[i] ? "AYE\n" : "NAY\n");
}
Example 2: Luogu P4178 Tree

Given a weighted tree with \(n\) nodes and a number \(k\), count the pairs of nodes in the tree at distance at most \(k\).

\(n\le 40000,k\le 20000,w_i\le 1000\)

Here we count the pairs of nodes whose distance lies in \([0,k]\), so we use a segment tree to maintain the distances and answer the queries.

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
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
constexpr long long MAXN = 2000010;
constexpr long long inf = 2e9;
long long n, a, b, c, q, rt, siz[MAXN], maxx[MAXN], dist[MAXN];
long long cur, h[MAXN], nxt[MAXN], p[MAXN], w[MAXN], ret;
bool vis[MAXN];

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

long long sum;

void calcsiz(long long x, long long fa) {
  siz[x] = 1;
  maxx[x] = 0;
  for (long long j = h[x]; j; j = nxt[j])
    if (p[j] != fa && !vis[p[j]]) {
      calcsiz(p[j], x);
      maxx[x] = max(maxx[x], siz[p[j]]);
      siz[x] += siz[p[j]];
    }
  maxx[x] = max(maxx[x], sum - siz[x]);
  if (maxx[x] < maxx[rt]) rt = x;
}

long long dd[MAXN], cnt;

void calcdist(long long x, long long fa) {
  dd[++cnt] = dist[x];
  for (long long j = h[x]; j; j = nxt[j])
    if (p[j] != fa && !vis[p[j]])
      dist[p[j]] = dist[x] + w[j], calcdist(p[j], x);
}

queue<long long> tag;

struct segtree {
  long long cnt, rt, lc[MAXN], rc[MAXN], sum[MAXN];

  void clear() {
    while (!tag.empty()) update(rt, 1, 20000000, tag.front(), -1), tag.pop();
    cnt = 0;
  }

  void print(long long o, long long l, long long r) {
    if (!o || !sum[o]) return;
    if (l == r) {
      cout << l << ' ' << sum[o] << '\n';
      return;
    }
    long long mid = (l + r) >> 1;
    print(lc[o], l, mid);
    print(rc[o], mid + 1, r);
  }

  void update(long long& o, long long l, long long r, long long x,
              long long v) {
    if (!o) o = ++cnt;
    if (l == r) {
      sum[o] += v;
      if (!sum[o]) o = 0;
      return;
    }
    long long 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]];
    if (!sum[o]) o = 0;
  }

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

void dfz(long long x, long long fa) {
  // tf[0]=true;tag.push(0);
  st.update(st.rt, 1, 20000000, 1, 1);
  tag.push(1);
  vis[x] = true;
  for (long long j = h[x]; j; j = nxt[j])
    if (p[j] != fa && !vis[p[j]]) {
      dist[p[j]] = w[j];
      calcdist(p[j], x);
      for (long long k = 1; k <= cnt; k++)
        if (q - dd[k] >= 0)
          ret += st.query(st.rt, 1, 20000000, max(0ll, 1 - dd[k]) + 1,
                          max(0ll, q - dd[k]) + 1);
      for (long long k = 1; k <= cnt; k++)
        st.update(st.rt, 1, 20000000, dd[k] + 1, 1), tag.push(dd[k] + 1);
      cnt = 0;
    }
  st.clear();
  for (long long j = h[x]; j; j = nxt[j])
    if (p[j] != fa && !vis[p[j]]) {
      sum = siz[p[j]];
      rt = 0;
      maxx[rt] = inf;
      calcsiz(p[j], x);
      calcsiz(rt, -1);
      dfz(rt, x);
    }
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (long long i = 1; i < n; i++)
    cin >> a >> b >> c, add_edge(a, b, c), add_edge(b, a, c);
  cin >> q;
  rt = 0;
  maxx[rt] = inf;
  sum = n;
  calcsiz(1, -1);
  calcsiz(rt, -1);
  dfz(rt, -1);
  cout << ret << '\n';
  return 0;
}
Example 3: Luogu P2664 A Game on a Tree

Every node of a tree has a color. Define \(s(i,j)\) as the number of colors on the path from \(\mathit{i}\) to \(\mathit{j}\), and \(\mathit{sum_{i}}=\sum_{j=1}^n s(i,j)\). Find \(sum_i\) for every \(1\leq i\leq n\). (\(1 \le n, c_i \le 10^5\))

This problem is a real test of how well you understand the idea of centroid decomposition and can apply it. It makes a good harder example and exercise for the technique.

The first step is a change of viewpoint. The problem defines \(\mathit{sum_i}\) as the sum, over all nodes, of the number of colors on the path from \(i\) to that node. Counting it that way is awkward in centroid decomposition, because it is hard to combine the information of two subtrees that hang from the current root. So we give \(\mathit{sum_i}\) a different meaning. For each color \(j\), let \(\mathit{cnt_j}\) be the number of paths that have \(i\) as an endpoint and contain color \(j\); then \(\mathit{sum_i}\) is just \(\sum \mathit{cnt_j}\). All this does is change what we look at: we now consider the contribution of each color to \(\mathit{sum_i}\). And \(\mathit{cnt_j}\) is easy to compute: every time we meet a new color, do \(\mathit{cnt_{col_u}}+=\mathit{size_u}\), where \(\mathit{size_u}\) is the size of the subtree of u, because every node of that subtree contributes one to the answer of \(u\) for this color.

In centroid decomposition we then only need to count two things separately:

  1. what the paths in the subtree that have the current root as an endpoint contribute to the root;
  2. what the paths whose LCA is the current root contribute to each node of the subtree.

Part 1 is easy. The recursion in centroid decomposition has at most \(\log{n}\) levels, so on every level we can afford to traverse the whole subtree, and we count with the definition of \(\mathit{sum_i}\) along the way.

For part 2, let \(d\) be a child of the current root \(u\), and let \(v\) be any node in the subtree of \(d\). The answer of \(v\) splits into two parts:

  1. Colors that occur on the path \((u, v)\). Let \(\mathit{num}\) be their number, and let \(\mathit{siz1}\) be the total size of all subtrees of \(u\) other than that of \(d\). These colors contribute \(\mathit{num}\times \mathit{siz1}\) to the answer of \(v\).
  2. Colors \(j\) that do not occur on the path \((u, v)\). Their contribution comes from the \(\mathit{cnt_j}\) of all subtrees of \(u\) other than that of \(d\), and this part of the answer is \(\sum_{j \notin (u, v)} \mathit{cnt_j}\).

That is the whole counting idea. See the reference code for the implementation details.

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
#include <algorithm>
#include <iostream>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
constexpr int N = 200005;
int h[N], nxt[N * 2], to[N * 2], c[N], gr;

void tu(int x, int y) { to[++gr] = y, nxt[gr] = h[x], h[x] = gr; }

using ll = long long;
int n, nn, siz[N], mn, rt;
bool vis[N];

void get_root(int u, int f) {
  siz[u] = 1;
  int mx = 0;
  for (int i = h[u]; i; i = nxt[i]) {
    int d = to[i];
    if (vis[d] || d == f) continue;
    get_root(d, u);
    siz[u] += siz[d];
    mx = max(mx, siz[d]);
  }
  mx = max(mx, nn - siz[u]);
  if (mx < mn) mn = mx, rt = u;
}

ll ans[N], sum;
int cnt[N], v[N];
// sum is kept equal to the sum of the cnt[i]
int nowrt;

void get_dis(int u, int f, int now) {  // now: number of colors on the current tree path (excluding u)
  siz[u] = 1;
  if (!v[c[u]]) {
    sum -= cnt[c[u]];  // remove what the earlier subtrees recorded for this color
    now++;
  }
  v[c[u]]++;
  ans[u] += sum + now * siz[nowrt];  // contribution to u of the paths through u
  for (int i = h[u]; i; i = nxt[i]) {
    int d = to[i];
    if (d == f || vis[d]) continue;
    get_dis(d, u, now);
    siz[u] += siz[d];
  }
  v[c[u]]--;
  if (!v[c[u]]) {
    sum += cnt[c[u]];  // backtrack
  }
}

void get_cnt(int u, int f) {
  if (!v[c[u]]) {
    cnt[c[u]] += siz[u];
    sum += siz[u];  // fold the subtree just traversed into cnt[i] and sum
  }
  v[c[u]]++;
  for (int i = h[u]; i; i = nxt[i]) {
    int d = to[i];
    if (vis[d] || d == f) continue;
    get_cnt(d, u);
  }
  v[c[u]]--;
}

void clear(int u, int f, int now) {
  if (!v[c[u]]) now++;
  v[c[u]]++;
  ans[u] -= now;
  ans[nowrt] += now;
  for (int i = h[u]; i; i = nxt[i]) {
    int d = to[i];
    if (vis[d] || d == f) continue;
    clear(d, u, now);
  }
  v[c[u]]--;
  cnt[c[u]] = 0;
}

void clear2(int u, int f) {
  cnt[c[u]] = 0;
  for (int i = h[u]; i; i = nxt[i]) {
    int d = to[i];
    if (vis[d] || d == f) continue;
    clear2(d, u);
  }
}

int son[N];

void divid(int u) {
  vis[u] = true;
  int tot = 0;
  nowrt = u;
  ans[u]++;
  for (int i = h[u]; i; i = nxt[i]) {
    if (vis[to[i]]) continue;
    son[++tot] = to[i];
  }
  siz[u] = sum = cnt[c[u]] = 1;
  v[c[u]]++;
  rep(i, 1, tot) {  // contributions of pairing each subtree with the nodes of all subtrees before it
    int d = son[i];
    get_dis(d, u, 0);
    get_cnt(d, u);
    siz[u] += siz[d];
    cnt[c[u]] += siz[d];
    sum += siz[d];
  }
  clear2(u, 0);  // clear the arrays; remember that memset must not be used
  siz[u] = sum = cnt[c[u]] = 1;
  for (int i = tot; i >= 1;
       --i) {  // contributions of pairing each subtree with the nodes of all subtrees after it
    int d = son[i];
    get_dis(d, u, 0);
    get_cnt(d, u);
    siz[u] += siz[d];
    cnt[c[u]] += siz[d];
    sum += siz[d];
  }
  v[c[u]]--;
  clear(u, 0, 0);                      // clear and collect the answers at the same time
  for (int i = h[u]; i; i = nxt[i]) {  // continue the centroid decomposition further down
    int d = to[i];
    if (vis[d]) continue;
    nn = siz[d], mn = n + 1, rt = 0;
    get_root(d, u);
    divid(rt);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  int u, v;
  rep(i, 1, n) cin >> c[i];
  rep(i, 2, n) cin >> u >> v, tu(u, v), tu(v, u);
  rt = 0, nn = n, mn = n + 1;
  get_root(1, 0);
  divid(rt);
  rep(i, 1, n) cout << ans[i] << '\n';
  return 0;
}

Edge centroid decomposition

As in centroid decomposition above, we pick an edge that splits the tree into two parts as evenly as possible (the \(\mathit{size}\) of the two subtrees that the edge joins should be as close as possible). Then we recurse into the left and right subtrees and collect the information.

But this does not work. Consider a star graph:

Star graph

When a node has many children of similar \(\mathit{size}\), edge centroid decomposition is unacceptably slow.

If the graph is a binary tree, the weakness that the star graph exposes disappears. So we turn a multiway tree into a binary tree.

Clearly, it is enough to build the tree the way a segment tree is built, like this:

Building the tree

Give the newly created nodes whatever information the problem calls for. For example, when counting path lengths, set the weight of every original edge to \(1\) and the weight of every new edge to \(0\).

As for the complexity: at most \(O(n)\) nodes are added, so the total complexity is \(O(n\log n)\).

Almost every centroid decomposition problem can also be solved by edge centroid decomposition (the constant factor differs, but not by enough to fail the time limit), so we give no example problems here.

Centroid tree

A centroid tree is a tree rebuilt from the original tree: the shape of the tree is changed so that its number of levels is always \(\log n\).

It is commonly used for problems with updates that do not depend on the shape of the original tree.

Analysis of the algorithm

We rebuild the original tree by repeatedly finding centroids, exactly as centroid decomposition does.

Make every centroid we find a child of the centroid of the level above. This gives a tree with \(\log n\) levels.

Because the tree has \(\log n\) levels, many brute-force approaches that would be too slow on the original tree have the right complexity on the centroid tree.

Implementation

A small trick: take the total size \(\mathit{tot}\) of the previous level of the recursion and subtract the size of the heavy child of the previous level's node. The result is the total size of the current level, so finding the centroid takes only one DFS.

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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

using IT = vector<int>::iterator;

struct Edge {
  int to, nxt, val;

  Edge() {}

  Edge(int to, int nxt, int val) : to(to), nxt(nxt), val(val) {}
} e[300010];

int head[150010], cnt;

void addedge(int u, int v, int val) {
  e[++cnt] = Edge(v, head[u], val);
  head[u] = cnt;
}

int siz[150010], son[150010];
bool vis[150010];

int tot, lasttot;
int maxp, root;

void getG(int now, int fa) {
  siz[now] = 1;
  son[now] = 0;
  for (int i = head[now]; i; i = e[i].nxt) {
    int vs = e[i].to;
    if (vs == fa || vis[vs]) continue;
    getG(vs, now);
    siz[now] += siz[vs];
    son[now] = max(son[now], siz[vs]);
  }
  son[now] = max(son[now], tot - siz[now]);
  if (son[now] < maxp) {
    maxp = son[now];
    root = now;
  }
}

struct Node {
  int fa;
  vector<int> anc;
  vector<int> child;
} nd[150010];

int build(int now, int ntot) {
  tot = ntot;
  maxp = 0x7f7f7f7f;
  getG(now, 0);
  int g = root;
  vis[g] = true;
  for (int i = head[g]; i; i = e[i].nxt) {
    int vs = e[i].to;
    if (vis[vs]) continue;
    int tmp = build(vs, ntot - son[vs]);
    nd[tmp].fa = now;
    nd[now].child.push_back(tmp);
  }
  return g;
}

int virtroot;

int main() {
  int n;
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v, val;
    cin >> u >> v >> val;
    addedge(u, v, val);
    addedge(v, u, val);
  }
  virtroot = build(1, n);
}