KokiYmgch's blog

By KokiYmgch, history, 7 years ago, In English

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!

  • Vote: I like it
  • +30
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

If you want centroid decomposition, you have to find the centroid first and then don't water it. That way, it'll wilt/decompose.

»
6 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    So all nodes are centroids? Yes

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    I think it should be n/2 instead of n.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

»
4 years ago, # |
  Vote: I like it -49 Vote: I do not like it

This is wrong!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -28 Vote: I do not like it

    And u find old posts to solved problem in running contest ?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

      Well, he isn't doing anything wrong, since in contests you can consult material and use third party code that was already made beforehand.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Top contestants do it all the time, and i am sure this is not prohibited ?!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I used this piece of code and got AC so its definitely not wrong.

    Thanks KokiYmgch

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I do not think you should comment on this post (or even if the post in on another website) during the competition.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks buddy! That really helped in this contest!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks a lot for this post. Turned out to be really helpful, even after 3 years!