eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Альпийская долина

Альпийская долина

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

В альпийской долине находится n деревень (пронумерованных 1 ... n), соединенных только n - 1 дорогами. Хотя из любой деревни все еще можно добраться до любой другой деревни, это может занять довольно много времени. Это особенно раздражает, когда Вам приходится покупать предметы первой необходимости, так как магазины имеются только в s из n деревень.

Этой зимой ситуация стала еще хуже из-за сильного снегопада. Поэтому было бы целесообразно либо покинуть долину, то есть добраться до единственной деревни e у горного перевала, соединяющего долину с внешним миром, либо, по крайней мере, купить достаточно припасов на следующие месяцы. Сегодня утром вы услышали по радио, что из-за снега одна из n - 1 дорог стала непригодной для использования - однако Вы не могли четко понять, какая из них.

Теперь Вы хотите узнать, можете ли Вы и Ваши друзья покинуть долину, и если нет, то как далеко каждый из Вас должен проехать, чтобы добраться до деревни с магазином. Вы не знаете, какая дорога заблокирована, а Ваши друзья живут в разных деревнях долины. Напишите программу, которая отвечает на этот вопрос для q комбинаций деревень и заблокированной дороги.

Входные данные

Первая строка содержит целые числа n (1n10^5), s, q (1q10^5) и e, где n - количество деревень, s (1sn) - количество магазинов, q - число запросов к Вашей программе, а e (1en) - деревня, которую следует достичь чтобы покинуть долину.

Каждая из следующих n - 1 строк содержит три целых числа a, b и w. Они означают что дорога длины w (1w10^9) соединяет деревни a и b (1an, 1bn).

Далее следуют s строк: каждая содержит одно целое число c означающая что в деревне c (1cn) находится магазин. Все эти строки разные, то есть ни одна деревня не содержит более одного магазина.

И наконец, каждая из q следующих строк содержит два целых числа i и r, означающие что i-ая дорога (1i < n, пронумерованы в порядке их перечисления) уже не активна, а Вы хотите узнать смогут ли Ваши друзья, проживающие в деревне r (1rn), покинуть долину, и если ответ отрицательный, то насколько далеко находится деревня с магазином.

Выходные данные

Выведите q строк. i - я строка должна содержать ответ на i - ый запрос. Соответствующая строка должна содержать строку "escape" (без кавычек), если имеется возможность покинуть долину; если нет, то строка должна содержать расстояние до ближайшей деревни с магазином или строку "oo", если достичь магазина невозможно.

Пример

Входные данные #1
5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5
Выходные данные #1
escaped
3
oo
Входные данные #2
10 2 5 4
7 2 3
4 8 3
9 10 1
6 7 3
9 2 3
10 1 2
8 2 2
5 2 1
3 8 2
8
7
2 1
1 5
8 4
6 2
7 7
Выходные данные #2
8
escaped
escaped
escaped
0

Примечание

На рисунке показана ситуация до того, как дорога станет непригодной для использования. Деревни с магазинами показаны серым цветом. Дороги помечены как "индекс / длина". Выход из долины находится в деревне 1.

prb9621.gif
Источник 2019 Baltic Olympiad in Informatics, День 1, 27 Апр - 2 Мая