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

Автор Petr, 10 лет назад, По-английски
  • Проголосовать: нравится
  • +95
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

SPOILER ALERT!!

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.