Given a tree with n<=2e5 nodes how do you find the nodes that are on the diameter of the tree?
Thanks!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
7 | adamant | 154 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
Given a tree with n<=2e5 nodes how do you find the nodes that are on the diameter of the tree?
Thanks!
Name |
---|
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).
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.
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.
How can you prove that this covers all of the diameters? Thanks
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.
https://loj.ac/problem/10159
It in Chinese but the problem is the same
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:
第一遍dfs,从0号点开始找到点r1,从r1进行第二遍dfs,找到点r2,再从r2进行第三遍dfs,找到点r3(这里,r2和r3都一定是某条直径的端点)。然后,我们从r2和r3开始执行更新,更新是指从r2/r3开始进行dfs,当dfs到某一结点时,如果该节点与r2/r3的距离等于树的直径,标记该点为直径上的点,并在递归回溯时把沿途的点都标记为直径上的点。这样之后,我们得到的就是所有直径上的点了。语言不太好表达,你可以看我的代码,我觉得写的还比较清楚。当然,我并不会证明这个算法的正确性orz