NeverSpot's blog

Can someone please explain Centroid Decomposition and why it works in O(nlogn)
By NeverSpot, history, 3 hours ago, In English

Hey Red Coders,

Recently, I have been trying to solve all the problems in the CSES tree section, but even after trying many things, I have failed to solve the last two problems. After searching for solutions, I learned that they can be solved using Centroid Decomposition.

I read some blogs and watched videos on YouTube, but I still can’t grasp the logic. Although I could pretend to understand it and copy paste code to complete the CSES section, I genuinely want to learn and understand why and how it works so that I will be able to solve questions based on it in the future.

I would greatly appreciate it if anyone is willing to explain it to me and help build my intuition around it.

Resources I have tried( although they are really great, but due to my limited knowledge I am not able to grasp the logic):

USACO guide Centroid section

Blog by Tanuj Khattar

Video by Colin Galen

Video by Gaurav Sen

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

»
2 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

It's very hard to explain because we don't know what it is that you are missing — it's hard to write a tutorial here in the comments that's better than all the attempts you've linked. Do you have problems understanding what a centroid decomposition is or are you having difficulty applying it. Maybe you can point out the first sentence in a tutorial of your choice that you don't understand?

Although I could pretend to understand it and simply code to complete the CSES section

This statement is surprising to me — it's usually not completely clear how to apply centroid decomposition, even if you know that it solves the problem.

→ Reply
  • »
    »
    119 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    In Tanuj Khattar's blog point number 3 says:

    Consider any two arbitrary vertices A and B, and the path between them (in the original tree) can be broken down into A–>C and C–>B, where C is the LCA of A and B in the centroid tree.

    But if we take a=2 and b=6, then their lca in the centroid tree will be 2 itself so 2—>2 and 2->6 point is if we are making 5 as a child, not an ancestor of, then how will propagation will work, and will it not miss to update 5... And one doubt I have is which is related to this if we have a bamboo tree of size 10^5, then we apply centroid decomposition, then many ancestors will become a children of their Child then how will we solve for subtree if your subtree does not contain all original elements of subtree...

    I think I should replace the word "simply" with "copy-pasting"

    → Reply
    • »
      »
      »
      7 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      then how will propagation will work, and will it not miss to update 5

      What do you mean by "propagation", or "updating 5"?

      Yes, the centroid decomposition of a tree may be totally different from the original tree. Descendants can become ancestors and so on. You cannot rely on anything like that holding in the new tree. What you do know is:

      • any path $$$u \to v$$$ in the original tree visits the LCA of $$$u$$$ and $$$v$$$ in the new tree;
      • the height of the new tree is $$$O(\log n)$$$.

      If you want to apply centroid decomposition, you must find a way to make use of those facts to somehow speed up your solution. This is kinda what I tried to say earlier too. Solving a problem with centroid decmposition is not simply a matter of copying the code of centroid decomposition: you have to figure out a way to use this decomposition.

      I have two new questions:

      1. Did you look the example solutions that Tanuj Khattar gives at the end of the blog?
      2. Is there a specific problem you are trying to solve using centroid decomposition?
      → Reply
»
112 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by NeverSpot (previous revision, new revision, compare).

→ Reply