PeterNaut's blog

Tree Question
By PeterNaut, 11 years ago, In English

In a weighted tree, how to find for every node the distance to its farthest node (in linear time)?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it
  1. Select an arbitrary node and set it as the root of the tree.
  2. For each node, go through its subtrees and calculate for each subtree the longest distance downwards from the current node to some node in the subtree. Store the longest and second longest distance among all the subtrees.
  3. Traverse the tree again and calculate for each node the longest distance through the parent. This can be calculated efficiently using the data collected in step 2. If the longest distance downwards from the parent corresponds to a path that goes through the current node, the second longest distance is used.

Now for each node the maximum distance is the maximum of the distances calculated in steps 2 and 3.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    Could you please explain the 3rd step a little bit more? I didn't understand the thing about second longest distance :( I was trying to solve IOI 2013 Dreaming... This thing is needed there :)

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

This was the main idea to solve problem dreaming in IOI 2013 , but the official solution is not published I don't know why. however ,the idea as pllk said

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

Another interesting solution:

Start at an arbitrary node, and find the node farthest from it. Then, find the node farthest from that node. This distance is the diameter of the tree (largest distance between two nodes).

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

First find the tree diameter using the algorithm given by aquamongoose and keep also the diameter nodes d1 and d2 (the tips). Then for all the nodes in the tree, the farthest node is either d1 or d2, (suppose that this is not the case, then you have a path that is longer than the diameter which is a contradiction, I hope you can derive the proof from this hint), then you just need to calculate the distance to d1 and d2 and pick the farthest, you can implement a (linear) LCA for this purpose or use the off-line Tarjan algorithm. The weights should be non-negative for this to work.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +15 Vote: I do not like it

    About last step: you don't have to use LCA, as distance from two offline-known vertexes can be found using a simple DFS ;-)

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You are right, you can just calculate all the distances from d1 using a DFS and the same for d2, anything else would be an overkill.

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

    Can you please elaborate more the proof? I don't understand why "suppose that this is not the case, then you have a path that is longer than the diameter which is a contradiction"

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

Can you give a link to that problem? (If it's somewhere on some online judge)

→ Reply