### KokiYmgch's blog

By KokiYmgch, history, 5 years ago, This article is about how to find the centroids of a tree. It can be computed with a trivial tree DP.

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!  Comments (20)
 » can you share some resource for studying about the dfs function you have used. I mean how to write a function within the same block.
•  » » Search for lambda functions in c++. (https://en.cppreference.com/w/cpp/language/lambda)There isn't much to it, just read carefully about the variable scope in lambdas.
 » If you want centroid decomposition, you have to find the centroid first and then don't water it. That way, it'll wilt/decompose.
 » 3 years ago, # | ← Rev. 2 →   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).So all nodes are centroids?
•  » » So all nodes are centroids? Yes
•  » » I think it should be n/2 instead of n.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   yes that's right it would be n/2 . . What is centroid of Tree? Centroid of a Tree is a node which if removed from the tree would split it into a ‘forest’, such that any tree in the forest would have at most half the number of vertices in the original tree. ~ GeeksForGeeks
•  » » » » Thanks, this is very clear cut answer for me. I didn't get the answer from the blog post. Once again thank u so much.
 » This is wrong!
•  » » And u find old posts to solved problem in running contest ?
•  » » » Well, he isn't doing anything wrong, since in contests you can consult material and use third party code that was already made beforehand.
•  » » » Top contestants do it all the time, and i am sure this is not prohibited ?!
•  » » » I think this is nearly the same solution needed in on of the problems in the current running contest, shouldn't it be blocked or something?
•  » » » » No, read Mike's blog "Rule about third party code is changing";
•  » » I used this piece of code and got AC so its definitely not wrong.Thanks KokiYmgch
•  » » I do not think you should comment on this post (or even if the post in on another website) during the competition.
 » Thanks buddy! That really helped in this contest!
 » Thanks a lot for this post. Turned out to be really helpful, even after 3 years!
•  » » Can someone explain why I am getting down-votes?
•  » » » Literally, I don't understand why do people down-vote others. You may up-vote if you liked some comment, else just ignore it....why to down-vote!