Блог пользователя GayHawk

How to do this in O(n)??
Автор GayHawk, 6 лет назад, По-английски

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

Thanks in advance. :)

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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:

.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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 .

→ Ответить