I am getting TLE for this SOLUTION. I tried to use heavy-light decomposition to solve it. Can anyone point to where the solution is slow ? Here is the reference solution, i did almost identical things. Please help
About implementation:
comment if you need more clarification 
Here are some of the places where I found an error in your code:
LCA Calculation : Anudeep’s code does LCA calculation in O(log n) using a precomputation of O(n log n). See lines 222- 226 in his code for details. Your code is too slow for this which can take O(n) in worst case.
Line number 99 - 106 : HLD function. The special case should directly call the HLD, else should come outside the if condition. See Anudeep’s code for further clarification.
I think all these changes may be enough. If you feel your question was answered mark it as accepted.
I don’t know how to say it politely, but you are wrong at point 1 and your point 2 does not affect the solution, please take it in a spirited manner. I got AC and let me explain why your point 1 and 2 do not hold ground.
LCA Calculation: The LCA function was almost correct, it had a bug on line 109
while(HEAD[i] != HEAD[j]){
if (L[j] > L[i]) swap(i, j) ;
//code
}
in the if statement, instead of comparing height of nodes, we had to compare height of Head of the chain to which node i and j belongs to. This procedure would give straight O(logn) worst case for finding LCA. Anudeep’s code is kind of overkill, we can find LCA using the Heavy chain information, in the same time.
In the former, there may or may not be a heavy child of a node, as you don’t usually encounter such nodes(unless the tree is horribly unbalanced). So there are more light edges in this version than Anudeep’s version.
In the later version, we are assured the every node is going to have a heavy child, because of the definition of maximum, in case of a tie, you can choose arbitrarily. Except the leaf node because they don’t even have a child at first place.
So if you don’t find a “Special Child” than you don’t have to care about anything, you can just exit the function as it is surely a leaf node, else call HLD on that “Special Child” and also on its other siblings. So, in Anudeep’s solution even leaf node goes to the “for” loop to discover they aren’t actually meant to.
In Anudeep’s version there are longer chains and less light edges than the former case, but it does not change the asymptotics of the algoritm/DS.
To assure you, i changes his code here LINK , i removed the pre-computation part, changed the LCA function and the “if” statement in HLD finction. it got AC(0.38s), Anudeep’s took 0.44s.
So, in short it was just my wrong/bugged LCA function 
.
Here is my AC version of the code SOLUTION.
I don’t know which version is faster( obviously because of constants and not asymptotically) and why. So feel free if you can throw some light on this. Thanks for taking time to look into my code and for the suggestions. Long may Anudeep Reign
Will u please help me in this prblm
Spent more than 7-8 hours on this, submitted a total of 14 codes and on every submission I got tle. Could not figure out why.
I don’t think there is anything wrong with my logic. The complexity of my solution is also nlog2n. I checked every while loop for infinite iterations; didn’t find any. I tried some of the available test cases from spoj toolkit but each of them worked fine. Is there a strict time limit or is there something else that I am missing.
Here is my [code]: dysO31 - Online C++0x Compiler & Debugging Tool - Ideone.com
Necessary comments are added in the code for anyone to understand.
Thanks in advance. Help would be much appreciated…
@ashwanigautam @likecs