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

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

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
  • Проголосовать: не нравится

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

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

→ Ответить