Parvej's blog

How to find both the centroids of a tree?
By Parvej, history, 6 years ago, In English

We know that a tree has either 1 or 2 centroids. I can find one centroid using simple dfs.

But, if a tree has 2 centroids, Is there a way to efficiently find the other one?

In case you don't know about centroids of a tree. See here

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
6 years ago, hide # |
 
Vote: I like it +26 Vote: I do not like it
  1. The two centroids have to be adjacent, you can confirm this with proof by contradiction.
  2. Once you find the first centroid, the second centroid only exists if the first centroid has an adjacent subtree of size exactly $$$N / 2$$$, and there can only possibly be one, so we know exactly who the other candidate centroid is and whether or not they're valid.
→ Reply
»
6 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

https://codeforces.me/blog/entry/57593

→ Reply