EduBrick

F. Максимальная тройка

1500 мс · 256 МБ · всё или ничего

Дано дерево на nn вершинах. Выберите три вершины так, чтобы сумма попарных расстояний между ними была максимальна.

Формат ввода

В первой строке nn (3≤n≤2⋅1053 \le n \le 2 \cdot 10^5). В каждой из следующих n−1n - 1 строк — числа vv и uu (1≤v,u≤n1 \le v, u \le n): ребро дерева.

Формат вывода

Выведите максимальную сумму попарных расстояний.

Примеры

ввод
3
1 2
1 3
вывод
4
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.