По задаче Е я придумал следующиее док-во.

Выберем две вершины А и B. Зафиксируем некоторую вершину С, ближайший к ней город с ярморкой обозначим К. Пусть w(A <-> K) <= w(K <-> B), если это не так, то можно просто "переназвать вершины".

Утверждается, что существует такая вершина С, что w(A <-> K) < w(C <-> K), если путь A <-> B не является диаметром дерева. Действительно, если A <-> B не является диаметром дерева, то найдется такая вершина A' или B', что w(A' <-> B) > w(A <-> B) или w(A <-> B') > w(A <-> B) (обозначу это суждение *). Таким образом можно находить более весомый путь и повторять эти действия пока не достигнем максимума. Если же A <-> B диаметр дерева, то такой вершины С не существует, если бы она существовала, то можно было бы найти путь большего веса, чем А <-> B, а это противоречит определению диаметра графа.

Вероность суждения (*) вытекает из корректности алгоритма поиска диаметра дерева.

1) 1й поиск в глубину/ширину этого алгоритма служит для того, чтобы перейти в вершину являющуюся листом дерева. (можно превести аналогию с тем, что, если А и B -- не листья дерева, то всегда можно найти точку С, что K = A и очевидно, что после замены А на C w(A <-> B) увеличится.)

2) 2й поиск в глубину предполагает, что мы его будем запускать из листа дерева и он найдет вершину, которая будет одним из концов радиуса дерева и к тому же будет самой удаленной от вершины из которой запускаем поиск. (Как это доказать я не знаю, просто поверим в это, ибо алгоритм работает). Соответственно если одна из вершин А B -- лист дерева (пусть это будет А), а другая не является концом одного из диаметров (пусть это будет B), то найдется вершина C (например, самая удаленная от А) и w(A <-> C) > w(A <-> B).

3) 3й поиск ищет второй конец диаметра, этот случай очень похож на 2й.

Любая критика приветствуется ;)