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

Автор PeterNaut, 10 лет назад, По-английски

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

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

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
  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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

    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 :)

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

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

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

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).

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

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.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

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

    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"

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

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