Автор та розробник: Святослав Бідзіля
Можна набрати часткові бали розв'язками за допомогою алгоритмів Дейкстри та Флойда, які шукають діаметр в довільному графі.
Щоб отримати вищі бали знайдемо особливість графу з умови. Оскільки граф з $$$n - 1$$$ ребром утворює дерево, то граф з $$$n$$$ ребер утворює дерево з одним циклом. Будемо розглядати граф, як цикл і кореневі дерева, з коренями в вершинах циклу. Далі є два різних випадки, де може бути діаметр. Або діаметр цього графа знаходиться в одному з дерев, або проходить через цикл.
Для першого випадку нескладно скористатися будь-яким відомим алгоритмом пошуку діаметра в дереві та для кожного дерева знайти діаметр сумарно за $$$O(n)$$$.
Для другого випадку важливо зрозуміти, що якщо діаметр проходить через дві вершини циклу (назвемо їх $$$u$$$ і $$$v$$$), то та частина діаметра, яка знаходиться в деревах з цими коренями доходить до найглибшого листа в такому дереві. Дійсно, якби вона доходила не до найглибшого листа, можна було б легко покращити відповідь, пішовши від вершини до найглибшого листа.
Знайдемо для кожної вершини циклу глибину найбільшого листа в її дереві (за допомогою dfs-у). Назвемо це число для $$$i$$$-ї вершини $$$h_i$$$. Назвемо відстанню між двома вершинами в циклі $$$dist(x, y)$$$ найкоротшу відстань по ребрах циклу між вершинами $$$x$$$ і $$$y$$$. Тепер задача звелася до максимізації $$$h_x + h_y + dist(x, y)$$$ по усім $$$x, y$$$ на циклі.
Як ефективно порахувати $$$dist(x,y)$$$? Перенумеруємо вершини циклу від $$$1$$$ до $$$m$$$. Запишемо всі ваги ребер циклу в масив $$$w$$$, так що вага ребра з вершини $$$i$$$ циклу в наступну записана в $$$w_i$$$. Нехай $$$ \sum_i^m w_i = S$$$. Тоді порахуємо відстань, якби ми йшли по одній стороні циклу $$$f(i, j) = \sum_{k = i}^{j - 1} w_k$$$. В іншому випадку, ми йдемо по іншій стороні циклу, тому використовуємо всі інші ребра. Тому $$$dist(i,j) = min(S - f(i, j), f(i, j))$$$.
Вже зараз задачу можна розв'язати на високий бал за $$$O(n^2)$$$, рахуючи шукану величину по всім вершинам циклу.
Для отримання повного балу можна помітити, що при фіксованому $$$i$$$ існує таке $$$k$$$, що при всіх вершинах $$$j$$$ від $$$i$$$ до $$$k$$$ $$$f(i, j) < S - f(i, j)$$$, а при всіх вершинах $$$j$$$ від $$$k$$$ до $$$i$$$ $$$f(i, j) >= S - f(i, j)$$$. Іншими словами, функція монотонна. Для всіх вершин з першої групи відстань дорівнює $$$f(i, j) = p_{j - 1} - p_{i - 1}$$$(Якщо ввести масив $$$p$$$ - префіксних сум масиву $$$w$$$), а діаметр на таких вершинах зводиться до $$$min(h_x + h_y + p_{y - 1} - p_{x - 1}) = min((h_x - p{x-1}) + (h_y + p_{y-1}))$$$. При фіксованому $$$x$$$ такий мінімум по всіх $$$j$$$ можна легко знайти за допомогою різних структур даних - дерева відрізків, підтримуючи множину усіх кандидатів і т.д. Сума для другої групи вершин схожа і підтримується аналогічно. Для пошуку оптимального $$$k$$$ можна використовувати бінарний пошук, або підтримувати $$$k$$$ методом двох вказівників.
При використанні сетів або дерева відрізків з'являється додатковий логарифмічний фактор, тому асимптотика рішення $$$O(n \log n)$$$.