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

Graph Theory Problem
Автор iLoveIOI, история, 5 лет назад, По-английски

Given a tree with n<=2e5 nodes how do you find the nodes that are on the diameter of the tree?

Thanks!

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

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

You can refer to this problem.

In its editorial, Mike provided a solution and the first half can show you how to do this(and I like Mike's way on it).

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

    What if there are multiple diameters with the same length and you have to print the points on any of the diameters? Thanks for the reply.

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

      Suppose the second DFS start from node u, then, you can get the value of dis[200010] where dis[i] means the diameter from i to u.

      Then, the maxinum value in dis[] is the length of diameter, let us call it "dia". Then, you can simply do the third DFS, starting from node u, using a vector to record the nodes on current path, once you arrive at some node j whose dis[j]==dia, output all nodes in vectors and they are one of diameters.

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

        How can you prove that this covers all of the diameters? Thanks

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

          In fact, I'm wrong and a counter case may be like this...(In this one, every nodes are on one of the diameter)

          Do you have the link to this problem? Now I have some ideas but still can't ensure that it's correct.

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

            https://loj.ac/problem/10159

            It in Chinese but the problem is the same

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
              ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

              With the hint of my friend, I got it AC and there's my code.

              In fact, what I have said at the beginning isn't that wrong. I just missed some details before.

              We still do 3 dfs on it. In the first dfs, we begin from 0 and get r1, which is the farest node from 0. In the second dfs, we begin from r1 and get r2 (there, r1->r2 is a diameter). In the third dfs, we begin from r2 and get r3(there, r2->r3 is also a diameter). Then, update the tree from r2 and r3. Here, updating means that dfs from r2/r3 , and when you find some node whose distance between r2/r3 is the length of diameter, mark it and update nodes on that path when backtracking. After that, you will get the answer. You can see my code for more details. However, I don't know how to prove it.

              Since it seems like that we are both poor in english, here's the solution in Chinese for you:

              chinese version
              → Ответить