Can someone please explain Centroid Decomposition and why it works in O(nlogn)
Difference between en3 and en4, changed 12 character(s)
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 simplycopy 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](https://usaco.guide/plat/centroid)↵
↵
[Blog by  Tanuj Khattar ](https://tanujkhattar.wordpress.com/2016/01/10/centroid-decomposition-of-a-tree/)↵
↵
[Video by Colin Galen](https://www.youtube.com/watch?v=-DmMLQCmz94&t=2624s&pp=ygUgd2h5IGNlbnRyb2lkIGRlY29tcG9zaXRpb24gd29ya3M%3D)↵
↵
[Video by Gaurav Sen](https://www.youtube.com/watch?v=-Lgda-6_AiY&t=322s&pp=ygUgd2h5IGNlbnRyb2lkIGRlY29tcG9zaXRpb24gd29ya3M%3D)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English NeverSpot 2024-11-28 22:00:36 12 Tiny change: 'nd it and simply code to c' -> 'nd it and copy paste code to c'
en3 English NeverSpot 2024-11-28 20:59:42 0 (published)
en2 English NeverSpot 2024-11-28 20:59:13 8
en1 English NeverSpot 2024-11-28 20:58:45 1333 Initial revision (saved to drafts)