12. Бусинки

Задача

По заданному дереву найдите максимальную длину простой цепочки, образованной соединёнными бусинками.

Входные данные

В первой строке дано число $N$ ($1 \leqslant N \leqslant 5 \cdot 10^5$) — количество бусинок. В следующих $N-1$ строках указаны пары чисел — соединённые бусинки.

Выходные данные

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

Примеры

стандартный ввод      стандартный вывод
2                      2
1 2

5                      3
2 1
2 3
2 4
2 5

Ограничения

  • Время: 2 секунды
  • Память: 256 мегабайт
Редакционный разбор Рассматриваем граф как дерево. Самая длинная цепочка — это диаметр дерева, длина наибольшего кратчайшего пути. Находим его двойным BFS/DFS: запускаем обход из произвольной вершины, находим самую дальнюю $v$, затем запускаем второй обход из $v$ и берём максимум расстояний. Он и будет ответом. Когда $N = 1$, диаметр равен $1$ по условию (одна бусинка). В реализации достаточно обработать этот случай отдельно или позволить алгоритму вернуть $0$ рёбер и добавить $1$. Оба обхода работают за $O(N)$ и укладываются по памяти.

Mentioned by