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

Автор furious, 12 лет назад, По-русски

Hey!

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

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

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

Use DFS!

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
  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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

      Yes, one time is enough.

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

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

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Wait, why 7?

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

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

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

              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 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

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

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

                  I finally understood. Thank you!

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

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

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

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

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

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

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

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);
}