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

Thanks in advance. :)

# | User | Rating |
---|---|---|

1 | tourist | 3539 |

2 | Radewoosh | 3464 |

3 | V--o_o--V | 3338 |

4 | Um_nik | 3307 |

5 | Petr | 3297 |

6 | ecnerwala | 3282 |

7 | LHiC | 3266 |

8 | wxhtxdy | 3264 |

9 | Vn_nV | 3182 |

10 | xyz111 | 3147 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 207 |

2 | Errichto | 176 |

3 | neal | 159 |

4 | Ashishgup | 158 |

5 | PikMike | 157 |

6 | Petr | 156 |

6 | majk | 156 |

8 | rng_58 | 155 |

9 | Um_nik | 154 |

9 | 300iq | 154 |

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/19/2019 02:13:59 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Let's make some vertex a root of the tree. Let

d_{x, y}be the length of the edge between vertecesxandy.Let

f_{v}be the maximal distance from vertexvto the vertex in its subtree. We will calcutate this value for all verteces using dfs:(or 0 if

vis leaf).Let

g_{v}be the maximal distance from vertexvto the vertex that is not in its subtree. We will calcutate this value for all verteces using dfs:(or 0 if

vis root).Then we will calculate

ans_{v}— answer to the problem. We will calcutate this value for all verteces:.

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?

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.

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.

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

uandv.Then we can prove that

answer(x) =max(dist(u,x),dist(v,x)), wheredist(a,b) is the distance between verticesaandb.Then we simply need to find the diameter (2x DFS) and then find find the distances from

uandvto all other vertices, which results in .