Айбар и Есма устали играть игру FAFI 2320, и придумали свою игру. Игра происходит на дереве размером n. Изначально, Есма на вершине u ставит свою фишку, а Айбар ставит свою фишку на вершине v. Игра происходит следующим образом:
Если фишки Айбара и Есмы стоят на одной вершине, игра заканчивается. В противном случае, Есма двигает свою фишку, по своему выбору, которая смежна с его текущей вершиной.
Если фишки Айбара и Есмы стоят на одной вершине, игра заканчивается. В противном случае, Айбар двигает свою фишку, по своему выбору, которая смежна с его текущей вершиной.
Возвращаемся к шагу 1.
Есма хочет как можно дольше оставаться наедине с Айбаром, из-за этого его цель сделать количество ходов как можно больше. А у Айбара есть срочные дела, он должен решать задачи из codeforces и его цель сделать игру как можно короче. Найдите количество ходов, которые Айбар совершит до окончания игры, если и Есма, и Айбар знают позицию и стратегию друг друга. Игроки играют оптимально.
Входные данные
В первой строке даны n, u, v. (1≤u,v≤n≤105,u≠v)
Далее в n−1 строках даны пары чисел (ai,bi)(1≤ai,bi≤n,ai≠bi) - ребра дерева.
Выходные данные
Выведите количество ходов, которые Айбар совершит до окончания игры.
написать на пайтон, js
Ответы
Ответ: ниже
Объяснение:Для решения этой задачи мы можем использовать поиск в глубину (Depth-First Search, DFS) для определения расстояния между вершинами u и v. Мы будем использовать два обхода DFS: один из u, чтобы найти путь до v, а другой из v, чтобы найти путь до u.
Во время первого обхода DFS мы будем сохранять расстояние от каждой посещенной вершины до u в массиве dist1[], а во время второго обхода DFS будем сохранять расстояние от каждой посещенной вершины до v в массиве dist2[]. Затем мы найдем наименьшее расстояние между u и v, а затем вычтем 1 (так как последний ход Айбара не приведет к перемещению).
реализация данного алгоритма на языке Python:
python
from collections import defaultdict
# Реализация класса графа
class Graph:
def __init__(self):
self.graph = defaultdict(list)
# Добавление ребра в граф
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
# Обход в глубину с подсчетом расстояния
def dfs(self, start, dist):
visited = [False] * (len(self.graph) + 1)
stack = []
stack.append(start)
dist[start] = 0
visited[start] = True
while stack:
s = stack.pop()
for i in self.graph[s]:
if not visited[i]:
visited[i] = True
stack.append(i)
dist[i] = dist[s] + 1
# Вычисление расстояния между вершинами u и v
def find_distance(self, u, v):
dist1 = [-1] * (len(self.graph) + 1)
dist2 = [-1] * (len(self.graph) + 1)
# Обход в глубину из u
self.dfs(u, dist1)
# Обход в глубину из v
self.dfs(v, dist2)
# Находим наименьшее расстояние между u и v
min_dist = float('inf')
for i in range(1, len(self.graph) + 1):
if dist1[i] != -1 and dist2[i] != -1:
curr_dist = dist1[i] + dist2[i]
min_dist = min(min_dist, curr_dist)
# Вычитаем 1, так как последний ход Айбара не приведет к перемещению
return min_dist - 1
# Чтение входных данных
n, u, v = map(int, input().split())
graph = Graph()
# Добавление ребер в граф
for i in range(n - 1):
a, b = map(int, input().split())
graph.add_edge(a, b)
# Вычисление расстояния между u и v
distance = graph.find_distance(u, v)
# Вывод результата
print(distance)
Пример входных данных:
6 1 4
1 2
2 3
3 4
4 5
4 6
Пример выходных данных:
2