mayankp's blog

Centroid decomposition problem
By mayankp, history, 7 years ago, In English

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?

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You do the exact same thing that you do in the N^2 solution, except you do it on the centroid decomposition tree instead.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    How would such a solution work though, because the O(n^2) solution I had in mind was to compute for every vertex the number of triples equidistant to that vertex, which I did by counting the number of vertices at a particular depth for each vertex, and then using some tricks with symmetric sums to get sums of products of triples of those. What is the solution that generalizes to allow for centroid decomposition?

    → Reply