В стране 40 городов, некоторые города соединены двусторонними авиарейсами. При этом, между любыми двумя городами существует только один разумный авиамаршрут (т. е. маршрут, на котором не надо пользоваться одним и тем же авиарейсом в разных направлениях).
Для каждого из городов вычислили авиарасстояние до столицы. Оно рассчитывается как минимальное количество рейсов, необходимое, чтобы долететь из этого города до столицы.
Для каждых двух городов А и В, соединённых авиарейсом, стоимость билета из города А в город В (также как и обратного) в марках равна наибольшему из авиарасстояний от А и В до столицы. В частности, билет до столицы из любого соединённого с ней прямым рейсом города стоит 1 марку; все остальные рейсы, вылетающие из этих городов, стоят 2 марки и так далее.
Петя много путешествовал (не только на самолётах) и в конце года оказалось, что он ровно по разу воспользовался каждым из авиарейсов (то есть, для каждых двух городов А и В, соединённых прямым авиарейсом, он слетал либо из А в В, либо из В в А, причём только в одну их сторон). Какое наибольшее количество марок он мог потратить на авиаперелёты?

Если построить граф, соединяя вершины (города) ребром, при наличии авиасообщения между ними, то получается дерево. Столицу выбираем корнем дерева, и рисуем его вниз от корня. Если где-то есть ветвление, но отсоединяем одну ветвь, и переносим её куда-то вниз (добавляя к "висячей" вершине). Стоимости поездок при этом только увеличиваются. Поэтому максимум достигается на "линейном" дереве, где нет ветвлений. Это значит, что из столицы 0 мы попадаем в город 1, из него в 2, и так далее, до города 39. Рейс из k-1 в k имеет стоимость k. Сумма стоимостей односторонних рейсов равна 1+2+...+39=39x40/2=780.

Если ответ по предмету Математика отсутствует или он оказался неправильным, то попробуй воспользоваться поиском других ответов во всей базе сайта.