Help on Hard Problem

Правка en1, от AksLolCoding, 2025-03-02 19:53:32

I have a problem as follows: You are given a weighted tree and a number L. You can do the following exactly once: choose a pair of nodes and add an edge of length L between them. Over all possible resulting graphs, what is the smallest possible diameter?

The editorial states that it is optimal for the chosen pair of nodes to both lie on a diameter of the original tree, but the proof is left as an exercise to the reader. I could not prove this, but can anyone explain why this is always optimal?

Теги tree, optimization

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский AksLolCoding 2025-03-02 19:53:32 522 Initial revision (published)