Centroid Decomposition in Trees Tutorial

Motivation problem: We have a tree consisting of n(<=10^5) nodes. We will consider the tree nodes indexed from 1 to n. We will also consider the first node to be initially painted red, and the other nodes — to be painted blue. The distance between two tree nodes v and u is the number of edges in the shortest path between v and u. We need to learn how to quickly execute queries of two types:

1. paint a specified blue node in red;
2. calculate which red node is the closest to the given one and print the shortest distance to the closest red node.

Your task is to write a program which will execute the described queries.

Comments: It does seem like RMQ(Range Minimum/Maximum but on trees. Of course these can be solved using segment trees(Heavy Light Decomposition). But there is a technique which can be used to solved these kind of problems with the same time complexity but shorter code. It’s called Centroid Decomposition. Even though its an advanced concept this video makes it clear to even beginners so do not be afraid if you just want to learn something new.

Please do like and subscribe for more videos like this solely focused on competitive programming and do comment your feedback in the video.