Задача №114169. Тройка вершин с максимальным расстоянием
Дано дерево на \(n\) вершинах. Требуется выбрать из них три так, чтобы сумма расстояний между ними была максимальна.
Первая строка каждого теста содержит натуральное число \(n\) - количество вершин в дереве (\(3 \leq n \leq 1\,000\,000\)). Следующие \(n - 1\) строк содержат по \(2\) натуральных числа \(v, u\) и описывают ребро дерева, соединяющее две вершины \(v\) и \(u\) (\(1 \leq v, u \leq n\)).
Выведите единственное число - максимальную сумму расстояний.
Решения, правильно раотающие на тестах, в которых \(n \leq 50\), будут оценитваться в \(25\) баллов.
Решения, правильно раотающие на тестах, в которых \(n \leq 500\), будут оценитваться в \(50\) баллов.
Решения, правильно раотающие на тестах, в которых \(n \leq 5000\), будут оценитваться в \(75\) баллов.
Решения, правильно раотающие на тестах, в которых \(n \leq 10^6\), будут оценитваться в \(100\) баллов.
3 1 2 1 3
4