Petr's blog

A week with a recent Open Cup
By Petr, 12 years ago, In English

http://petr-mitrichev.blogspot.com/2015/03/this-week-in-competitive-programming_17.html

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

»
12 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

SPOILER ALERT!!

Regarding to that problem about tree you described — I think that decomposing whole tree into layers of centroids should work.

→ Reply
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Right; and constants were so low (TL=9s) that even simple decomposition of tree into blocks by sqrt(N) vertices (which in comparison to centroid decomposition is like sqrt-decomposition comparing with segment tree for arrays) was fast enough to pass.

    → Reply