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/
Try binary lifting. It has a query time of O(logN). I really liked Errichto's tutorial on it.
The adjacency list is not cleared at the end of each testcase, so there might be cycles in the graph formed by the union of the trees in all testcases.