В стране 100 городов, между ними действует несколько беспосадочных авиалиний так, что от любого города до любого можно добраться, возможно, с пересадками. Для каждой пары городов вычислили наименьшее количество перелётов, необходимых чтобы добраться от одного до другого. Назовём транспортной затруднённостью страны сумму квадратов этих 4950 чисел. Какое наибольшее значение может принимать транспортная затруднённость? Ответ должен быть дан в виде числа (в десятичной системе счисления).
Сначала докажем, что транспортная затруднённость наибольшая в случае, когда города связаны «по цепочке».
Действительно, можно считать граф деревом (иначе выкинем часть рёбер так, чтобы осталось дерево — затруднённость увеличится). Выберем в дереве самый длинный путь. Допустим, что есть вершины, не входящие в этот путь. Тогда среди них найдётся висячая вершина x (то есть вершина, в которую ведёт только одно ребро). Пусть y — ближайшая к x вершина самого длинного пути. Перенесём всю «ветку», отходящую от y и содержащую x, в конец самого длинного пути, более удалённый от y. Заметим, что в результате попарные расстояния между вершинами в пределах «ветки» не изменились, расстояния между вершинами вне ветки — тоже. При этом легко видеть, что для каждой вершины ветки сумма квадратов расстояний до всех остальных вершин возросла. Действительно, если k — расстояние от некой вершины z ветки до y, то набор расстояний от z до вершин вне ветки (включая y) был
а стал 
Такими «перевешиваниями» можно привести граф к виду цепочки, причём затруднённость всё время будет возрастать; значит, для цепочки она максимальна.
Теперь посчитаем затруднённость для «цепочки». Задача сводится к нахождению суммы
Обозначим
Как известно,
(это можно доказать по индукции). Заметим, что искомая сумма равна
Ответ: 8 332 500.