Найти диаметр дерева
Вам дано дерево с v вершинами, и ваша задача — найти его диаметр. Диаметр определяется как длина пути между двумя наиболее удалёнными вершинами.
Ввод
Первая строка входных данных содержит одно целое число v (1 ≤ v ≤ 100 000).
В следующих v-1 строках записаны пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), указывающие, что вершина v1 соединена с вершиной v2 и наоборот.
Вывод
Программа должна вывести диаметр заданного дерева.
Примеры
Ввод | Вывод |
|---|---|
3 1 2 1 3 | 2 |
5 1 2 1 3 3 4 3 5 | 3 |
Подсказка 1
Можно несколько раз выполнить DFS (поиск в глубину) из разных вершин.
Подсказка 2
Сначала можно запустить DFS из вершины 1 и найти самую удалённую вершину (поскольку это дерево и в нём нет циклов, мы можем сделать это без BFS).
Затем запустите DFS из найденной самой удалённой вершины и найдите вершину, которая от неё дальше всего.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB