Help on Hard Problem

Revision en1, by 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?

Tags tree, optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English AksLolCoding 2025-03-02 19:53:32 522 Initial revision (published)