30
ньют саламандер в очередной раз наблюдает за детенышами нюхлей. ему интересно, так ли
хорошо они ищут золото, как и взрослые особи.
для испытаний ньют взял n коробок и соединил их n − 1 двунаправленными тоннелями так,
чтобы между каждыми двумя коробками был ровно один простой путь. ньют называет тупиком
любую коробку, в которую можно попасть только по одному тоннелю.
ньют хочет разместить нюхля в одном тупике, а в каком-то другом тупике разместить золотую
монету. однако так как нюхль еще маленький, ньют хочет выбрать тупики так, чтобы детеныш как можно меньше тоннелей при поиске монеты.
ваша ньюту найти минимальное число тоннелей, которое придется пройти детенышу нюхля, чтобы найти монету при оптимальном выборе тупиков.
формат входных данных
в первой строке дано целое число n — число коробок (2 ⩽ n ⩽ 10^5).
в следующих n − 1 строках заданы по два числа ai, bi — номера коробок, которые соединены
i-м тоннелем (1 ⩽ ai, bi ⩽ n).
гарантируется, что между любыми двумя коробками, существует ровно один простой путь.
формат выходных данных
выведите одно число — минимальное расстояние, которое нужно пройти нюхлю, чтобы найти
монету.
примеры
стандартный ввод
5
1 2
1 3
2 4
2 5
стандартный вывод
2
Задача состоит в том, чтобы найти минимальное число тоннелей, которое нужно пройти детенышу нюхля, чтобы найти монету при оптимальном выборе тупиков.
Для начала, нам необходимо построить такой граф, чтобы между каждыми двумя вершинами был ровно один путь. В данной задаче у нас дано число коробок n, и мы соединяем их n-1 тоннелями. Для представления данного графа нам потребуется использовать структуру данных "список смежности".
Способ представления графа в виде списка смежности следующий: мы создаем список, где каждому элементу i соответствует список смежных с ним вершин.
В данной задаче, у нас есть n коробок и n-1 тоннель. Последовательно обозначим каждую коробку буквой от a до n
Для наглядности, построим такой граф:
a-----b-----d
| |
c e
Теперь нам нужно найти оптимальные тупики для детеныша и монеты. Если мы выберем какой-то тупик для детеныша, то монету нужно выбрать в другом тупике, чтобы минимизировать количество тоннелей, которые нужно пройти для ее нахождения.
Мы можем заметить, что монету и детеныша нам нужно разместить в разных тупиках. Если мы выберем тупик для монеты и "заблокируем" его (то есть выберем тупик для детеныша в другом месте), то мы сможем минимизировать длину пути для нахождения монеты.
Итак, алгоритм решения этой задачи:
1. Сначала необходимо построить граф, используя входные данные. Для этого создадим список смежности с помощью входных данных.
2. Найдем все тупики (вершины, у которых только один ребенок) в графе. Запишем их в отдельный список.
3. Для каждого тупика в списке, найдем расстояние до каждого другого тупика в графе, проходя только по ребрам. Для этого воспользуемся алгоритмом обхода графа в ширину или алгоритмом Дейкстры.
4. Найдем максимальное расстояние между теми тупиками, где мы можем разместить детеныша и монету. Это и будет минимальная длина пути, которую нужно пройти детенышу, чтобы найти монету.
В данном примере (по входным данным) ответом будет число 2, так как минимальное число тоннелей, которое придется пройти детенышу нюхля для нахождения монеты, равно 2.