| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
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://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.