Найти диаметр дерева
Вам дано дерево с
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