furious's blog

By furious, 12 years ago, In Russian

Hey!

Tell me plz how to find the diameter of a tree using DP. Thanks in advance! :)

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

| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use DFS!

»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it
  1. Pick any vertex as source vertex.
  2. Find the most distant vertex from the source. Make this vertex new source.
  3. Repeat step 2 two times.
  4. Distance between the source and the the most distant vertex from the source is diameter.
  • »
    »
    12 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    that's not dynamic programming. but thanks, anyways.

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

    can you explain in step 3 why have you asked to repeat step 2 , two times. once i have the farthest node from root (lets mark it as A)only one more time DFS(A) should yield another node(let say B) that is farthest from A node and the question seem to be solved. Please correct me if i am wrong.

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

      Yes, one time is enough.

      I guess he had meant that you need to do step 2 two times in total.

»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Another way. Run DFS from the root. In each subtree, we find the length of the longest path from the root of this subtree to some descendant of it. It is clear, how we can compute the answer for some vertex. We solve the problem for each of its children, and the answer for this vertex is 1+max where max is the longest path from one of the children to some descendant of it.

Then the answer to the problem is the maximum value over the , for each vertex and two of its children.

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

    Thanks for the idea, but I think it won't work at this test, for example

    1 2 2 3 3 4 3 5 3 6

    Because 1 has only left subtree

    • »
      »
      »
      12 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Well, of course, we need to consider also , for the root, if it has only one child. Thanks for the note.

      • »
        »
        »
        »
        12 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        and here comes another question: why do we find the path that covers the root of the subtree. I think that's not true. For example,

        1 2
        2 3
        3 4
        2 5
        5 6
        6 7
        1 8

        Your answer is 7, but it should be 5. Thanks for the reply.
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Wait, why 7?

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

            cause dfs(2) = 5, dfs(8)=0 5+1+0+1=7, if I understand you correctly)

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

              No, no, dfs doesn't return that value. Think of it in this way: first we calculate only max values for each of the vertices, and only then we try to find a pair of two children of some vertex which maximizes the 2 + max1 + max2. So, for example, in this case:

              • dfs(3) = 1 (path 3-4)
              • dfs(5) = 2 (path 5-6-7)
              • dfs(2) = 3 (path 2-5-6-7)
              • dfs(1) = 4 (path 1-2-5-6-7)
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                why dfs(1) = 4? it should be 5 And dfs(2) should return 5 (4-3-2-5-6-7), shouldn't it?

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

                  I counted the number of edges, not the number of vertices on the path.

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

                  Yes, but 4-3-2-5-6-7 is the longest path and amount of edges is 5

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

                  ############################################

                  Yes, and when we look at vertex 2 (after dfs), we see that child 3 has max1 = 1 edges, and child 5 has max2 = 2 edges. So we can relax our answer to 2+1+2=5 edges.

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

                  I finally understood. Thank you!

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

                  Great! And I think it can be counted as DP. (:

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

                  sorry to disturb you after 7 years, can you tell me how to find end nodes of diameter?

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

                  Check the editorial of problem F from Codefoces #615(Div.3)

»
4 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

store the best and second best depths of children of every node in dp[node].

Here's the code for storing all values

int ans = 0;
void dfs(int a, int p, vector<vector<int>>& adj, vector<pii>& dp){
    pii& pa = dp[a];  

    for(auto x: adj[a]){
        if(x != p){
            dfs(x, a, adj, dp);
            if(dp[x].X + 1 >= pa.X){
                pa.Y = pa.X;
                pa.X = dp[x].X + 1;
            }
            else if(dp[x].X + 1 > pa.Y){
                pa.Y = dp[x].X + 1;
            }
        }
    }
    ans = max(ans, pa.X + pa.Y);
}