Distance between two nodes in a tree weighted

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/

Solution

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.