Skip to content

Tree Divide and Conquer

Centroid Decomposition

Centroid decomposition is suitable for handling large-scale tree path information problems.

Example 1 Luogu P3806【Template】Centroid Decomposition 1

Given a tree with \(n\) vertices and edge weights, answer \(m\) queries. For each query, given \(k\), determine whether there exists a pair of vertices with distance exactly \(k\) on the tree.

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

We first arbitrarily choose a node as the root \(\mathit{rt}\). All paths entirely within its subtree can be divided into two types: those passing through the current root node and those not passing through the current root node. For paths passing through the current root node, they can be further divided into two types: those with the root node as one endpoint, and those where neither endpoint is the root node. The latter can be obtained by merging two chains of the former type. Therefore, for the enumerated root node \(rt\), we first compute the contribution to the answer from paths within its subtree that pass through this node, then recursively solve for paths not passing through this node in its subtrees.

In this problem, for paths passing through the root node \(\mathit{rt}\), we first enumerate all its child nodes \(\mathit{ch}\), and compute the distances from all nodes in the \(\mathit{ch}\) subtree to \(\mathit{rt}\) with \(\mathit{ch}\) as the root. Let \(\mathit{dist}_i\) denote the distance from node \(i\) to the current root \(rt\), and \(\mathit{tf}_{d}\) indicate whether there exists a node \(v\) in previously processed subtrees such that \(\mathit{dist}_v=d\). If a query \(k\) satisfies \(tf_{k-\mathit{dist}_i}=true\), then there exists a path of length \(k\). After computing whether the edges connected in the \(\mathit{ch}\) subtree can form an answer, we add these new distances to the \(\mathit{tf}\) array.

Note that when clearing the \(\mathit{tf}\) array, we cannot simply use memset. Instead, we should add the previously used \(\mathit{tf}\) positions to a queue and clear them one by one. This ensures the time complexity.

During centroid decomposition, each node is processed once per level across all recursive calls in that level. Assuming there are \(h\) recursive levels in total, the overall time complexity is \(O(hn)\).

If we always select the centroid of the subtree as the root node, we can guarantee the minimum number of recursive levels, resulting in a time complexity of \(O(n\log n)\). Therefore, centroid decomposition is also commonly known as centroid decomposition in international competitive programming circles.

Please note that after reselecting the root node, it is essential to recalculate the subtree sizes. Otherwise, even a seemingly minor change may lead to incorrect time complexity or correctness issues.

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: process subtree d[], connected component size cnt
   dp: maximum subtree f[], tree centroid rot
   get: calculate distance from point to centroid t[], top
   calc: centroid decomposition bu[] length bucket
   hd to nx wg: adjacency list (chain forward star) for graph storage
   ak[] as[]: offline query processing
   ok[]: points that have become centroids in centroid 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\) vertices and an integer \(k\), count the number of vertex pairs whose distance on the tree is less than or equal to \(k\).

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

Since here we query the number of vertex pairs with distances in \([0,k]\), we use a segment tree to support maintenance and 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 Tree Game

A tree where each node is assigned a color. Define \(s(i,j)\) as the number of distinct colors on the path from \(\mathit{i}\) to \(\mathit{j}\), and \(\mathit{sum_{i}}=\sum_{j=1}^n s(i,j)\). For all \(1\leq i\leq n\), compute \(sum_i\). (\(1 \le n, c_i \le 10^5\))

This problem tests the understanding and application of centroid decomposition ideas and is suitable as a challenging example and exercise for centroid decomposition.

First, we need to realize a transformation. The problem defines \(\mathit{sum_i}\) as the sum of the number of colors on paths from \(i\) to all nodes. However, with this definition, it is difficult to aggregate answers in centroid decomposition because merging information from two subtrees branching from the current root is not straightforward. Therefore, we consider transforming the meaning of \(\mathit{sum_i}\). For each color \(j\), let \(\mathit{cnt_j}\) denote the number of paths with one endpoint \(i\) that contain color \(j\). Then \(\mathit{sum_i}\) is actually \(\sum \mathit{cnt_j}\). This transformation shifts the perspective to consider the contribution of each color to \(\mathit{sum_i}\). And \(\mathit{cnt_j}\) can be easily computed: whenever a new color is encountered, simply perform \(\mathit{cnt_{col_u}}+=\mathit{size_u}\), where \(\mathit{size_u}\) is the size of \(u\)'s subtree, meaning all nodes in this subtree contribute once to \(u\)'s answer regarding this color.

Considering the centroid decomposition process, we only need to separately handle:

  1. Paths within the subtree that have the current root as an endpoint, contributing to the root.
  2. Paths whose LCA is the current root, contributing to each node within the subtree.

Part 1 is relatively straightforward. Since the recursion depth in centroid decomposition does not exceed \(\log{n}\), at each level we can traverse all subtrees, and during this traversal we can use the definition of \(\mathit{sum_i}\) to accumulate statistics.

For part 2, let the current root node be \(u\) and one of its child nodes be \(d\). Take any node \(v\) in \(d\)'s subtree. Then the answer for \(v\) can be divided into two parts:

  1. Colors that have appeared on the path \((u, v)\), denote the count as \(\mathit{num}\). Let \(\mathit{siz1}\) be the total size of all subtrees of \(u\) except \(d\). Then the contribution of these appeared colors to \(v\)'s answer is \(\mathit{num}\times \mathit{siz1}\).
  2. Colors \(j\) that have not appeared on the path \((u, v)\). Their contribution comes from \(\mathit{cnt_j}\) of all subtrees of \(u\) except \(d\). This part of the answer is \(\sum_{j \notin (u, v)} \mathit{cnt_j}\).

The above covers all statistical ideas. For implementation details, refer to the code.

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 keeps track of the sum of cnt[i] in real-time
int nowrt;

void get_dis(int u, int f, int now) {  // now is the number of colors on the current tree chain (excluding u)
  siz[u] = 1;
  if (!v[c[u]]) {
    sum -= cnt[c[u]];  // Subtract color information that has already appeared in previous subtrees
    now++;
  }
  v[c[u]]++;
  ans[u] += sum + now * siz[nowrt];  // Count the contribution of paths passing through point u to 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];  // Integrate the information of the newly traversed subtree 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) {  // Count the contribution from combinations of nodes in each subtree and all previous subtrees
    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 array, note: cannot use memset
  siz[u] = sum = cnt[c[u]] = 1;
  for (int i = tot; i >= 1;
       --i) {  // Count the contribution from combinations of nodes in each subtree and all subsequent subtrees
    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 while also counting answers
  for (int i = h[u]; i; i = nxt[i]) {  // Continue point divide and conquer downwards
    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 Decomposition

Similar to centroid decomposition above, we select an edge to split the tree as evenly as possible into two parts (making the \(\mathit{size}\) of the two subtrees connected by the edge as close as possible). Then recursively process the left and right subtrees and aggregate information.

However, this approach has a flaw. Consider a star graph:

Star Graph

We find that when a node has multiple children with similar \(\mathit{size}\), applying edge decomposition leads to unacceptable time complexity.

If the graph is a binary tree, the drawback of edge decomposition in the star graph can be avoided. Therefore, we consider transforming a multi-way tree into a binary tree.

Clearly, we can construct it similarly to how a segment tree is built, like this:

Construction

Assign appropriate information to the newly created nodes according to the problem requirements. For example: when counting path lengths, assign weight \(1\) to original edges and weight \(0\) to newly created edges.

Analyzing the complexity, we find that at most \(O(n)\) additional nodes are added, so the total complexity is \(O(n\log n)\).

Almost all problems solvable by centroid decomposition can also be solved by edge decomposition (with constant factor differences, but usually not a bottleneck), so no separate examples are provided here.

Centroid Tree

A centroid tree is a reconstructed tree that changes the original tree's structure to achieve a stable \(\log n\) depth.

It is commonly used to solve dynamic problems unrelated to the original tree structure.

Algorithm Analysis

We reconstruct the original tree by repeatedly finding centroids through centroid decomposition.

Connect each found centroid as a child to the centroid from the previous layer, forming a tree of depth \(\log n\).

Since the tree has \(\log n\) layers, many brute-force approaches that were originally inefficient become feasible with correct complexity on the centroid tree.

Implementation

A small trick: each time, subtract the heavy child size of the node from the previous layer's total size \(\mathit{tot}\) to obtain the total size for the current layer. This way, finding the centroid requires 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);
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用