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):
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?
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.
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"
Auto comment: topic has been updated by NeverSpot (previous revision, new revision, compare).