darkshadows's blog

By darkshadows, 6 years ago, In English

Hello CodeForces Community!

I felt Centroid Decomposition as a very interesting and powerful technique when I first come along it. My friend, Baba has written a well designed and insightful blog on it. Also, I am including some other resources that can be very well found on CF only.


  1. https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree
  2. http://codeforces.com/blog/entry/10533
  3. http://ipsc.ksp.sk/2009/real/solutions/l.html
  4. http://codeforces.com/blog/entry/12982
  5. http://petr-mitrichev.blogspot.com/2015/03/this-week-in-competitive-programming_22.html
  • Vote: I like it
  • +58
  • Vote: I do not like it

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

This link is helpful too for understanding centroid decomposition. https://sai16vicky.wordpress.com/2014/11/01/divide-and-conquer-on-trees-centroid-decomposition/

3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hey guys! I made a video editorial using the blogpost by Tanuj. https://youtu.be/-Lgda-6_AiY

Feel free to leave your comments and suggestions :-)


10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the benefit of performing CD instead of calculating the distances for the original tree. Is it a fact that the CD tree is balanced?