The way to find the centroids of a tree

Revision en1, by KokiYmgch, 2018-02-06 21:36:30

The centroid(s) of a tree is, the vertice(s) whose all subtrees' size is not more than n(the size of the whole tree).

A tree may have one centroid or may have two centroids. If it has two centroids, they are always connected (otherwise, the tree can't have n vertices).

You can find these vertices by checking the size of each subtree, doing DFS. When the size of a subtree is s, the size of the other part is n - s.

vector<int> Centroid(const vector<vector<int>> &g) {
int n = g.size();
vector<int> centroid;
vector<int> sz(n);
function<void (int, int)> dfs = [&](int u, int prev) {
sz[u] = 1;
bool is_centroid = true;
for (auto v : g[u]) if (v != prev) {
dfs(v, u);
sz[u] += sz[v];
if (sz[v] > n / 2) is_centroid = false;
}
if (n - sz[u] > n / 2) is_centroid = false;
if (is_centroid) centroid.push_back(u);
};
dfs(0, -1);
return centroid;
}


Usage: By using g, the adjacent lists of a tree, get a vector with one or two centroids.

vector<vector<int>> g(n);
/*
construct a tree
*/
auto centroids = Centroid(g);
if (centroids.size() == 1) {
int c = centroids;
//
} else if (centroids.size() == 2) {
int c1 = centroids;
int c2 = centroids;
//
} else {
assert(false);
}


You may sometimes want to find the centroids of any subtree by cutting the original tree. When cutting a tree, you don't really 'cut' the tree. Instead, just make the vertice die. By ignoring died vertices, you can re-implement the Centroid function like this way.

vector<int> Centroid(int root, const vector<vector<int>> &g, const vector<bool> &dead) {
static vector<int> sz(g.size());
function<void (int, int)> get_sz = [&](int u, int prev) {
sz[u] = 1;
for (auto v : g[u]) if (v != prev && !dead[v]) {
get_sz(v, u);
sz[u] += sz[v];
}
};
get_sz(root, -1);
int n = sz[root];
vector<int> centroid;
function<void (int, int)> dfs = [&](int u, int prev) {
bool is_centroid = true;
for (auto v : g[u]) if (v != prev && !dead[v]) {
dfs(v, u);
if (sz[v] > n / 2) is_centroid = false;
}
if (n - sz[u] > n / 2) is_centroid = false;
if (is_centroid) centroid.push_back(u);
};
dfs(root, -1);
return centroid;
}


Don't forget to reuse sz, or it's going to be slow (or if you like, use map).

By the way, when you do Centroid Decomposition, you don't need to know 2 centroids of the tree. Therefore, if you just want to find 'a' centroid of a dynamic tree, you can implement this in the following way:

int OneCentroid(int root, const vector<vector<int>> &g, const vector<bool> &dead) {
static vector<int> sz(g.size());
function<void (int, int)> get_sz = [&](int u, int prev) {
sz[u] = 1;
for (auto v : g[u]) if (v != prev && !dead[v]) {
get_sz(v, u);
sz[u] += sz[v];
}
};
get_sz(root, -1);
int n = sz[root];
function<int (int, int)> dfs = [&](int u, int prev) {
for (auto v : g[u]) if (v != prev && !dead[v]) {
if (sz[v] > n / 2) {
return dfs(v, u);
}
}
return u;
};
return dfs(root, -1);
}


This is very fast, because it returns a centroid shortly after it finds a centroid for the first time.

Thank you for your reading! I'll write an article on centroid decomposition later! #### History

Revisions Rev. Lang. By When Δ Comment
en1 KokiYmgch 2018-02-06 21:36:30 4268 Initial revision (published)