Блог пользователя Parvej

How to find both the centroids of a tree?
Автор Parvej, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +26 Проголосовать: не нравится
  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.
→ Ответить
»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

https://mirror.codeforces.com/blog/entry/57593

→ Ответить