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

Queries on Tree
Автор LashaBukhnikashvili, 11 лет назад, По-английски

I need problems about Queries on Tree.

which data structures need problems same as above?

Can you guys suggest problems?

Any help will be appreciated very much :)

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

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

Heavy-Light Decomposition.

Wiki

E-maxx (Russian)

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

I didn't understand clearly. But if you are looking for tree query related problems, you can try QTREE , QTREE2 , QTREE3 , QTREE4 , QTREE5 , QTREE6

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

    if you don't mind would you please give some hints on how to solve QTREE4? I'm quite sure it can be done with heavy-light decomposition but I couldn't get a solution! I need to keep track of the currently longest path and second longest path and the third and so on to be able to switch between them after white nodes get blackened.

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

Heavy light decomposition (with Segment tree) problem for beginners : http://acm.timus.ru/problem.aspx?space=1&num=1553 If you need the code, you can see my code: https://sites.google.com/site/kc97ble/container/heavylight-cpp

→ Ответить