Centroid decomposition problem

Revision en3, by mayankp, 2016-12-22 06:38:17

The following POI problem: main.edu.pl/en/archive/oi/21/hot, which asks one to find the number of vertices of a tree equidistant from one vertex, has a fairly simple O(n^2) solution, which is sufficient to get full points. However, when looking at the solution, there appeared to be a O(n log n) solution that used what appeared to be centroid decomposition, though it was hard to tell, since the solution was in Polish and google translate doesn't do that good of a job. What is a solution to this problem in O(n log n) that uses centroid decomposition, and are there any other solutions that get O(n log n) or better?

Tags centroid decomposition, polish oi

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English mayankp 2016-12-22 06:38:17 0 (published)
en2 English mayankp 2016-12-22 06:37:08 574
en1 English mayankp 2016-12-22 06:31:12 132 Initial revision (saved to drafts)