№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Can someone explain the logic given below for this problem.
One easy to implement solution is using 2 Breadth First Searches (BFS). Start a BFS with a random node and store the last node encountered before search ends. This last node will definitely be one of the ends of the diameter (Why?). Now run a second BFS from this node and you will end on the other end of the diameter.
Thanks
Название |
---|
imagine a tree's diameter is drawn as a vertical line and other branches are connected to that line. from any node x, farthest node from x is always one of end points of diameter line. if there exists any node y, which is nether end point of diameter line and is farthest from x, then diameter line should be changed, to a line from (y to x) + (x to one of end points of diameter line which is farther from x). you can draw and check this. in conclusion, you can always find one of end point of diameter by finding farthest node from any node x. (i'm not good at english, hope it helped.)
Hope this helps
I highly recommend you watch this
This is the blog where the method has been proved, and this explains it using a diagram.
Doing a bfs is fine. It also finds the distances from a vertex $$$u$$$ to all other vertexes $$$v$$$.
.
dfs and bfs are both $$$O(n)$$$ (since this is a tree) so I have no idea what you are talking about.
Why do you need a proof about it? Just believe in it
So what do you want to say? You became master with just believing in algorithms?
Yes
https://mirror.codeforces.com/blog/entry/60440?#comment-443004
Yes
Because it feels right.
Hey, in case someone is looking for an intuitive explanation: here's a video explaining it using a pretty surprising way to look at the problem.