Petr's blog

By Petr, 10 years ago, In English
  • Vote: I like it
  • +95
  • Vote: I do not like it

»
10 years ago, # |
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.

  • »
    »
    10 years ago, # ^ |
      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.