LashaBukhnikashvili's blog

Queries on Tree
By LashaBukhnikashvili, 11 years ago, In English

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 :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Heavy-Light Decomposition.

Wiki

E-maxx (Russian)

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply