hi,i have spent my whole day in solving and debugging the LCA problem n spoj but still not able to find the bug plz need help. below is the problem link and my solution
@mrinal_29 In your function euler tour you should keep
if(v[a[n][i]]==false)
dfs(a[n][i],height+1);
b.pb(n);
this in curly brackets because b.pb(n) has to be done only when your node is not visited if it is visited it means that you are pushing that child again which is already traversed. Note that you are supposed to retrace the path not travel it again. Moreover is b your euler_tour, if yes you should have stored the indices instead of vertices. Euler tour works on the basis of order in which you move over certain connected vertices. You can make a tree and try to find whether it gives right Euler tour.
I will try to find some bugs till that time.
Can you explain what are you trying to do. Maybe my method is different from you but you should have calculated the minimum in range f[u] and f[v] in euler tour where euler tour store the numbering of indices in which you have travelled across the tree. But you min function is not doing that I guess.
Can you explain your approach?
hi vishesh, thnx for the reply. in my approach i used a tree of pairs for making segment tree in which the first pair stores the height of the index encountered and second of pair stored the index value which i encountered in the euler tour , i applied what u said but sadly it did not get accepted.i will put a more elaborative code for better understanding , again thnx for reply
Although i cannot suggest much but yes you can go for Sparse Table instead of Segment Tree. It is easy to implement and used when we don’t have any updates only queries. In case of updates (if any) segment tree is preferred. U r welcome.
thnx vishesh for the suggestion