GayHawk's blog

How to do this in O(n)??
By GayHawk, 6 years ago, In English

How do I calculate the length of the path to the farthest node for all nodes in a weighted tree?

Thanks in advance. :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Let's make some vertex a root of the tree. Let dx, y be the length of the edge between verteces x and y.

Let fv be the maximal distance from vertex v to the vertex in its subtree. We will calcutate this value for all verteces using dfs:

(or 0 if v is leaf).

Let gv be the maximal distance from vertex v to the vertex that is not in its subtree. We will calcutate this value for all verteces using dfs:

(or 0 if v is root).

Then we will calculate ansv — answer to the problem. We will calcutate this value for all verteces:

.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a bit unclear what you are asking. Are you asking about the longest path from the root to any of the nodes, or are you asking about the longest path between any two vertices? Also, are any of the weights negative?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was asking about the length of the path to the farthest vertex reachable for every node. And all weights are non negative.

    Extremely sorry for the inconvenience.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No worries, I actually think I should have read it more carefully. In that case, you can use the fact that for all vertices, the farthest vertex will be the endpoint of a diameter of the tree. Thus, you can find the diameter with two DFS' in O(n) time, and calculate the distance from each endpoint of the diameter with another extra DFS.

      → Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Imagine you found a diameter of your tree. Let the endpoints be u and v.

Then we can prove that answer(x) = max(dist(u, x), dist(v, x)), where dist(a, b) is the distance between vertices a and b.

Then we simply need to find the diameter (2x DFS) and then find find the distances from u and v to all other vertices, which results in .

→ Reply