n хижин с номерами от 0 до n - 1, соединённых тропами из массива trails: запись [u, v] — двусторонняя тропа между хижинами u и v. Тропы образуют дерево: от любой хижины до любой другой есть ровно один путь.
Запрос requests[i] = [start, end, hut] означает: группа идёт по пути из start в end, а друг из хижины hut хочет присоединиться. Найдите хижину на пути группы (включая start и end), до которой от hut меньше всего переходов по тропам.
Верните массив ответов: i-й элемент — номер такой хижины для i-го запроса.n=6, trails=[[0, 1], [1, 2], [2, 3], [1, 4], [4, 5]], requests=[[0, 3, 5], [3, 2, 0], [5, 4, 5]] → [1, 2, 5]
Маршрут 0 → 1 → 2 → 3; от хижины 5 ближе всего до точки 1 (через 4, два перехода). Маршрут 3 → 2; от 0 до 2 два перехода, до 3 — три, так что встречаемся в 2. В третьем запросе хижина 5 сама лежит на маршруте.
n=2, trails=[[0, 1]], requests=[[1, 1, 0]] → [1]
Маршрут состоит из одной точки 1, она и есть ответ.
n=6, trails=[[0, 1], [1, 2], [2, 3], [1, 4], [4, 5]], requests=[[0, 3, 5], [3, 2, 0], [5, 4, 5]]
[1, 2, 5]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 80 тестов на сервере, включая скрытые.