Centroid Decomposition in C++
In this article, we will discuss Centroid Decomposition in C++ with its example.
What is Centroid Decomposition?
Centroid decomposition is a powerful technique for efficiently solving tree-related problems. It involves finding special nodes called centroids, which split the tree into subtrees, with no subtree having more than half the total nodes. This decomposition allows for efficient "divide and conquer" approaches.
Centroids
A centroid of a tree is a node v such that, when removed, the resulting subtrees all have at most half the number of nodes in the original tree. In mathematical terms, for each child u of v, the size of the subtree rooted at u is less than or equal to half the size of the entire tree (N / 2).
Finding Centroid
We can find a centroid using a depth-first search (DFS) with a twist. Here's the algorithm:
- Start at an arbitrary node: Choose any node in the tree as the starting point.
- Calculate subtree sizes: During the DFS traversal, keep track of the size of each subtree rooted at the current node (subtree_size).
- Check for centroid: If a node's subtree size is greater than half the total tree size (subtree_size > N / 2), it's not a centroid. Kindly move to the child node with the largest subtree size (since it's most likely closer to a centroid).
- Repeat DFS from the child: Continue DFS from the child node with the largest subtree, recalculating subtree sizes.
- Centroid found: If a node reaches a point where all its children's subtrees are less than or equal to half the total size, it's a centroid.
Problem:
Several problems can benefit from the breakdown above.
Xenia, the programmer, has a tree consisting of n nodes. We'll consider tree nodes indexed from 1 to n. Furthermore, we'll assume that the first node was originally painted red while the subsequent nodes were painted blue.
The number of edges in the shortest path connecting two tree nodes, v and u, represents their distance from one another.
Xenia needs to become proficient at answering two kinds of inquiries quickly:
- Determine which red node is closest to the provided one by painting a specified blue node in red, then report the shortest distance to the closest red node.
- It is your responsibility to create software that will carry out the given questions.
Implementation:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> II;
typedef vector<II> VII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long int LL;
typedef unsigned long long int ULL;
const int N = int(1e5) + 10;
const int LOGN = 20;
const int INF = int(1e9);
set<int> g[N];
int par[N], sub[N], level[N], ans[N];
int DP[LOGN][N];
int n, m;
/* Using centroid Decomposition of a tree */
/*----------- Pre-Processing ------------*/
void dfs0(int u) {
for (auto it = g[u].begin(); it != g[u].end(); it++) {
if (*it != DP[0][u]) {
DP[0][*it] = u;
level[*it] = level[u] + 1;
dfs0(*it);
}
}
}
void preprocess() {
level[0] = 0;
DP[0][0] = 0;
dfs0(0);
for (int i = 1; i < LOGN; i++) {
for (int j = 0; j < n; j++) {
DP[i][j] = DP[i - 1][DP[i - 1][j]];
}
}
}
int lca(int a, int b) {
if (level[a] > level[b]) swap(a, b);
int d = level[b] - level[a];
for (int i = 0; i < LOGN; i++) {
if (d & (1 << i)) {
b = DP[i][b];
}
}
if (a == b) return a;
for (int i = LOGN - 1; i >= 0; i--) {
if (DP[i][a] != DP[i][b]) {
a = DP[i][a];
b = DP[i][b];
}
}
return DP[0][a];
}
int dist(int u, int v) {
return level[u] + level[v] - 2 * level[lca(u, v)];
}
/*----------------- Decomposition Part --------------------------*/
int nn;
void dfs1(int u, int p) {
sub[u] = 1;
nn++;
for (auto it = g[u].begin(); it != g[u].end(); it++) {
if (*it != p) {
dfs1(*it, u);
sub[u] += sub[*it];
}
}
}
int dfs2(int u, int p) {
for (auto it = g[u].begin(); it != g[u].end(); it++) {
if (*it != p && sub[*it] > nn / 2) {
return dfs2(*it, u);
}
}
return u;
}
void decompose(int root, int p) {
nn = 0;
dfs1(root, root);
int centroid = dfs2(root, root);
if (p == -1) p = centroid;
par[centroid] = p;
for (auto it = g[centroid].begin(); it != g[centroid].end(); it++) {
g[*it].erase(centroid);
decompose(*it, centroid);
}
g[centroid].clear();
}
/*----------------- Handle the Queries -----------------*/
void update(int u) {
int x = u;
while (true) {
ans[x] = min(ans[x], dist(x, u));
if (x == par[x]) break;
x = par[x];
}
}
int query(int u) {
int x = u;
int ret = INF;
while (true) {
ret = min(ret, dist(u, x) + ans[x]);
if (x == par[x]) break;
x = par[x];
}
return ret;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u - 1].insert(v - 1);
g[v - 1].insert(u - 1);
}
preprocess();
decompose(0, -1);
fill(ans, ans + n, INF);
update(0); // first node is initially painted red
while (m--) {
int t, v;
cin >> t >> v;
v--;
if (t == 1)
update(v);
else
cout << query(v) << endl;
}
return 0;
}
Output:
![Centroid Decomposition in C++/>
<!-- /wp:html --></p>
</div>
<div class=](https://static.tutorialandexample.com/cpp/centroid-decomposition-in-cpp1.png)