iLoveIOI's blog

Graph Theory Problem
By iLoveIOI, history, 4 years ago, In English

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

Thanks!

  • Vote: I like it
  • -7
  • Vote: I do not like it

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

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).

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

    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.

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

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            https://loj.ac/problem/10159

            It in Chinese but the problem is the same

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              ← Rev. 2   Vote: I like it +1 Vote: I do not like it

              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
              → Reply