SPOJ QTREE4

I am trying to solve the problem QTREE4 but can not get any working solution. I have seen some solutions use Heavy-Light decomposition and Heap but could not make out the algorithm by seeing their code. Can anybody help me in solving this problem ? Thank you in advance.

I found a link which has the solution…go through it u may get an idea of what algo u have to use…!!

Can anyone give suggestions ??