You can view the original codeforces blog here.
Centroid
If you have ever read about graph theory or participated in a Codeforces contest, you've likely heard about trees. In this tutorial, I'll be talking about centroid, an important vertex that helps you to solve many problems.
To comprehend what centroid is, you need to first be familiar with trees, and also know a little bit about divide and conquer.
The following tutorial is accompanied by the following two videos I prepared to explain centroid:
Centroid #1 | Full Explanation and Implementation
Centroid #2 | Bonus and Interesting facts
Some sample problems
The following problems can be solved using centroid:
Ciel the Commander (I solve this problem for you in my first video)
Distance in Tree (Can also be solved without centroid, but it is a good training for implementing centroid)
Kirito in Memeland (Also needs segment tree)
Close Vertices (Also needs segment tree)
Feel free to suggest additional problems.
Definition
A centroid is a vertex that, if you remove it from the tree, all connected components afterward have at most n/2 vertices.
You might have these questions now:
- Why should such a vertex exist?
- How can we find it?
- How this vertex can help us solve problems?
Proof of existence and the algorithm to find it
We address both questions simultaneously. In other words, we prove the existence of a centroid by discovering it. Once found, its existence is validated.
We root the tree arbitrarily (let's say at vertex 1) and determine the subtree size for each vertex.
Initially, we start from vertex 1. In each step, if the current vertex has a child with a subtree size exceeding n/2, we move to that vertex. Eventually, we will stop moving. We argue that the vertex we are in is our centroid. (Detailed proof in the video)
How centroid helps us
If you are familiar with divide and conquer, "n/2" likely strikes a chord!
As the number of vertices is halved at each step, removing the centroid, selecting one of the resulting connected components, and repeating this process over and over again, each time reduces the tree's size by half. Hence, how many times we repeat our process? Yes, at most log(n). :) (each time, the number of vertices is halved, we start from n vertices, so we have at most lg(n) steps)
Solving a problem using centroid
In the video, I solve 'Ciel and Commander'. Make sure to watch it to comprehend how centroid can aids to solve a problem.
How many centroids?
In the video, I prove that there are two cases: 1. We have only one centroid. 2. We have two centroid, and there are adjacent.
Most of the time, the first case happens.
An alternative definition for centroid + Proof
There is also another definition for centroid.
If we define S(v), as the sum of the distances of all the vertices in the tree from vertex v (unweighted distance), then vertex c is a centroid if and only if S(c) is minimal. I prove this in detail in the video.
The rest of the topic is covered in my second video about centroid.
The second proof
Now that we know a vertex with the minimal value of S is a centroid, it's clear we have one because there's a vertex with a minimal S value. :)
In order to find the centroid, you can calculate the value S for all the vertices (using dynamic programming) and report the minimal one as your centroid.
The third proof (and the most incredible one)
For each edge, see how many vertices are on each side of this edge. Direct the edge toward the side with more vertices (if equal, direct it randomly).
With n vertices and n-1 edges, there will be a vertex with zero outgoing edges. (Otherwise, we needed to have at least n edges) That vertex is a centroid. (Why?)
I hope this tutorial helps you. I'm trying to help everyone get familiar with algorithms and competitive programming easily. Your feedback is very important to me. Please share your comments and suggestions. If these tutorials aid, I will dedicate myself to releasing at least one every Friday. If you want to support this initiative, liking the videos and subscribing to the channel can be very helpful.
Thank you,
Shayan
Great content! Keep it up, it helped me a lot understanding the concepts of centroid.
Would love to see more future advanced contents!
Would love to see more contents like this in future.