game_changer007's blog

iit-k monthly contest
By game_changer007, 9 years ago, In English

Hi how to solve this question.

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Let X and Y is the beginning and the end of one of the longest paths in the tree. Longest possible path length from any vetex z is equal to maximal distance between z and x, and between z and y. To find distance between pairs of vertices you can find their LCA(Least Common Ancestor) in Log(n).

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

    you have to find the longest path which is called as the diameter of the tree. Let us suppose U and V are the pair of vertices such that U->V is one diameter of the tree. Now it is gurantee that the longest path from any node X will be the maximum of the two paths

    1. From X to U

    2. From X to V

    You can do 2 times DFS once from the vertex U and other from the vertex V , side by side maintaining distance from both vertices ... This way you can solve this problem without the knowledge of LCA and the time complexity of this solution is O(V+E)

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

Another way to solve this problem is straightforward DP on a tree.

First of all we have to find Down[i] — length of longest path starting from vertex i and going down. To find it you need to pick best value among sons of given vertex, this part can be implemented with a single DFS.

After that we can find Up[i] — length of longest path starting from vertex i and going up. Here you have 2 possibilities. Let's say that j is a parent of i. Then Up[i] may be either Up[j]+1, if we'll move up from j, or Down[q]+2, where q is some other son of j, if we'll choose to move down from j instead of moving up. This part of solution also can be implemented with a single DFS.

And now it is clear that answer for every vertex is max(Down[i],Up[i]).

→ Reply