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

Автор notTehlka, история, 6 лет назад, По-английски

Can someone explain the logic given below for this problem.

Logic

Source

Thanks

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

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +17 Проголосовать: не нравится

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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Hope this helps

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

I highly recommend you watch this

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

This is the blog where the method has been proved, and this explains it using a diagram.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Why do you need a proof about it? Just believe in it

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

Because it feels right.

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

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.