Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Centroid Decompostition in QTREE
Автор radhey_maa, история, 9 лет назад, По-английски

Can QTREE be solved using centroid decomposition. I solved QTREE5 using the method, but I am struggling to solve QTREE using the method. Problem

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

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

I see two solution ideas: 1) HLD + segment tree. 2) Link-Cut Tree (almost no extra code)

I don't think centroid decomposition is a good approach here due to the updates required. Although there may be a solution using centroid decomposition trees but that solution doesn't seem as obvious to me.

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

    Thanks, but I just wanted to practice the technique. I don't know if this means that all QTREEs can be solved using centroid decomposition or it just involves distances on trees.

    → Ответить