My Question is very straight forward.
A weighted tree is given. We must find the distance between two given nodes.
since number of queries are very high(around 75000) each time bfs be timed out so I tried different way to do that.
My algorithm is like this :
I ran dfs from vertex 0 and calculated distance from root(0) to all vertex something like this
depth[v]=depth[u]+w,where u is parent of v and w is weight b/w (u,v)
Once I calculated depth of all node using dfs and 2^j th parent of each node(Assume I know how to do that).I calculated LCA for (u,v) asked for each query.
Then I calulated distance like this
distance between (u,v)=depth[u]+depth[v]-2*depth[lca(u,v)]
But I am not getting correct verdict as expected.Is my algorithm correct or am I missing something crucial.Guidance needed :)
P.s Incase anyone wants to see my implementation-Link http://paste.ubuntu.com/13129038/
Your approach sounds reasonable, but looking at the linked code I suggest you try a small example (e.g. with 3 nodes in the tree) and check the contents of the parent array carefully.
As far as I can see, the only lines changing the contents of the parent array are:
memset(parent,-1,sizeof parent);
and
parent[i][j]=parent[i-1][parent[i-1][j]]
so I believe the contents of parent will always equal -1.
Perhaps you need a base case setting parent[0][j] equal to the parent of j?
Also, it is not quite clear from the code whether you are using depth to mean a count of the number of edges, or a sum of the weights of all the edges. For the distance calculation to work you need a sum of weights, but for the LCA algorithm to work you may find you need to use the count of edges.