algorithmgraphlowest-common-ancestor# 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.

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?