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

heavy light decomposition

Автор Ahmed_Morsy, 10 лет назад, По-английски

I tried to solve problem e in round 199 xenia and tree using heavy light decomposition but I couldn't figure out the whole idea anyone ?

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

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

EDIT: Wrong idea. As Xellos said: every problem has a simple, clear, obviously incorrect solution :D

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

This problem can be solve easier with centroid decomposition.

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

    what is that "centroid decomposition" ?

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

      Centroid of a tree is a vertex that after deleting it, every component will have at most n/2 vertices. You can easily prove its existence. So, using this, you can use divide and conquer on trees and if your time complexity for each merge(conquer) is O(f(n)), then the total complexity would be ; Because you did it at most times on each vertex(every time, the size of the component a vertex u is in it would be half of the previous one).

      → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Almost give up, but it works. Handle the segment carefully and not affect other segment values (by limit range update between chain root and chain tail of each chain) https://mirror.codeforces.com/contest/342/submission/111296661

→ Ответить