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