yusayura's blog

SPOJ Qtree5 solution using HLD
By yusayura, history, 6 years ago, In English

Hey there! I've recently been learning heavy light decomposition, and I read somewhere that SPOJ QTREE5 problem can be solved using this data structure;

I tried to find a good solution to this problem with HLD but wasn't much successful, so I will appreciate it if somebody gives me a little hint on solving it by heavy light decomposition.

By the way, my own solution was a really scary and hard_to_implement one, using tons of DPs and segment trees and I'm not sure if I can code it at the first place :(

Thanks in advance :)

  • Vote: I like it
  • +5
  • Vote: I do not like it

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

It is solvable with centroid decomposition.

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

    Yeah, I've heard about that;

    The thing is, I wanna understand HLD approach as well.

    → Reply