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[0];
//
} else if (centroids.size() == 2) {
int c1 = centroids[0];
int c2 = centroids[1];
//
} 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!
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.
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.
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
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?