Розбір

Для того, щоб розв'язати цю задачу, необхідно зрозуміти, куди додавати ребра, та які ціни їм надавати. Для того, щоб максимізувати наш результат, будемо з'єднувати вершини, які знаходяться близько у нашому дереві. Нам потрібно додати велику кількість ребер, тому в новому графі у деяких вершин буде багато сусідів. Якщо ми будемо шукати відстані від деякої такої вершини, то нам потрібно, щоб множини сусідів сусідів нашої вершини сильно перетинались, інакше від нашої вершини можна буде за декілька ребер прийти до будь-якої вершини графа. Звідси, можна вибрати декілька вершин та з'єднати їх всіх між собою, отримавши те, що зветься клікою.

У ці кліки будемо додавати вершини, які з'єднані між собою в дереві та відокремлені від інших вершин, щоб додавання цих ребер не сильно змінило відстані між іншими вершинами. Тому, можна брати піддерева та робити з них кліки. Розмір цих клік не може бути більше, ніж $k+1$, щоб ми не додали дуже багато ребер до вершин. Тому, можливий такий алгоритм для додавання ребер:

Знаходимо розміри всіх піддерев нашого дерева, та шукаємо найбільшу кліку, яку можна зробити (Якщо у нас мало додаткових ребер, то можна взяти такий розмір піддерева, щоб зробити майже кліку та використати всі ребра). Після цього додаємо необхідні ребра та забуваємо про ці вершини, та продовжуємо розбиття.

Тепер поставимо ваги на всі ребра. В кліці дуже багато ребер, тому відстані між вершинами кліки будуть дуже маленькими (якщо якесь ребро у кліці дороге, то є безліч можливостей його обійти). Тому, можна зробити всі ребра у кліці дуже дешевими. Інших ребер у графі буде дуже мало, тому що доданих ребер значно більше, ніж початкових. Тому можна зробити інші ребра найдорожчими у графі. Додатково, у клік є межові вершини — ті, які мають ребра до вершин не з кліки. Їх не дуже багато, та всі мінімальні шляхи, які йдуть через кліку, або між вершиною кліки та іншими вершинами, проходять через ці вершини. Тому, можна зробити ребра між вершинами межі та іншими вершинами кліки дорогими, тому що багато шляхів проходить через них. Також можна не додавати ребра між вершинами межи, щоб шляхи через кліку два рази йшли дорогими ребрами кліки, а не один, як раніше.

Для подальшого покращення результатів можна модифікувати алгоритм пошуку піддерева для перетворення на кліку шляхом пошуку того, наскільки це зменшує відстані між вершинами графа, чи шляхом перебору.