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?
if i get problem correctly -
basically the diameter is the tree`s biggest pain is the longest path so adding an edge on it chops off that worst stretch if you pick nodes of the diameter, youre not hitting the main problem so youre missing out on the best shortcut
This is what I think...
Imagine that we add an edge of weight L between two nodes a and b.
There are two possible cases:
For the second case, if the new diameter does not contain the newly added edge, this means that the added edge has no effect on the diameter. Since we are only interested in reducing the diameter, we can ignore this case because the placement of the edge doesn't matter.
Now, we focus on the first case, where the new diameter includes the new edge in some way. This leads to two subcases:
(A) The new diameter increases.
If the diameter increases, it means that the longest shortest path in the graph has become larger than before. However, our goal is to minimize the diameter, so to prevent the diameter from increasing, the best strategy is to place the edge between a pair of nodes that already lie on the original diameter. This guarantees that the new longest path does not exceed the previous diameter, as we can always fall back on the original diameter if needed, ensuring that the diameter remains at least the same as before.
(B) The new diameter decreases.
To achieve a smaller diameter, we need to shorten the longest shortest path in the graph. The only way to do this is to directly reduce the length of the original diameter. This means that we must place the new edge between two nodes that lie on the current diameter, as connecting any other nodes would not affect the longest path.
in both cases is always optimal to add the new edge between two nodes that are already on the current diameter of the tree.
Thanks! Most of this is very helpful, but I don't think that you can just "ignore" the second case. If the existing diameter is from c to d, the new edge might reduce the distance from c to d, which could allow another path that is not affected by the new edge to become the new diameter.
Well, what I thought was... if the new edge is not part of the new diameter but still changes the previous diameter, that's a contradiction cause the edge affects the original diameter while also not being part of the new longest path. If the diameter changes, it must be due to the newly added edge.