Посмотрим на множество, которое является оптимальным ответом. Если его диаметр (максимальный по длине путь) имеет хотя бы $$$3$$$ ребра, то удалим среднее в этом диаметре. Множество распалось на два связных, в каждом из которых находится хотя бы две вершины. Тогда хотя бы в одном из них среднее значение будет не меньше. Значит в одном из оптимальных ответов длина диаметра не более двух.
Если длина диаметра $$$1$$$, то это просто две соседних вершины. Если же длина диаметра равняется двум, то такой граф выглядит как несколько вершин, соединённые с одной центральной. Для каждой центральной переберём количество соседей, которые мы возьмём. Ясно, что выгодно брать максимальные по полезности вершины. Тогда для каждой вершины отсортируем соседей по убыванию полезностей, и переберём, какой префикс получившегося массива мы возьмём. Среди всех найденных средних значений найдём максимальное. Это и будет ответом.