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

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

Can someone explain the logic given below for this problem.

Logic

Source

Thanks

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

»
4 года назад, # |
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.)

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

Hope this helps

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

I highly recommend you watch this

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

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

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

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

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

Because it feels right.

»
3 года назад, # |
  Проголосовать: нравится +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.