I stuck at a problem lca,I tried to solve it using square root decomposition Here is my implementation https://ideone.com/Q6AbaO

processing time O(n)

query time O(sqrt(n))

Result: Getting TLE

But when i read comments on spoj most of people O(n) query was accepted. Can any one tell me where I am doing wrong?

My code is very well explained here with every line of code https://www.geeksforgeeks.org/sqrt-square-root-decomposition-set-2-lca-tree-osqrth-time/