알프스 계곡
시간 제한3초메모리 제한512 MB
가중치가 있는 나무에서 상점들과 출구가 주어질 때, 간선 하나가 제거된 상황에서 특정 마을에서 출구까지 또는 가장 가까운 상점까지의 거리를 구하는 질의에 답한다.
문제
알프스 계곡에는 N개의 마을이 있고(1번부터 N번까지), 이들은 N − 1개의 도로로 연결되어 있다. 어떤 마을에서든 다른 마을로 갈 수는 있지만 시간이 꽤 걸릴 수 있다. 기본 생필품을 사야 할 때 특히 불편한데, N개의 마을 중 S개에만 상점이 있기 때문이다.
올겨울에는 폭설로 상황이 더 나빠졌다. 따라서 계곡을 떠나거나, 즉 계곡과 외부를 잇는 고개에 있는 유일한 마을 E에 도달하거나, 최소한 앞으로 몇 달 동안 쓸 생필품을 충분히 사 두는 편이 좋다. 오늘 아침 라디오에서 눈 때문에 N − 1개의 도로 중 하나를 쓸 수 없게 되었다는 소식을 들었지만, 어느 도로인지는 분명히 알아듣지 못했다.
이제 당신과 친구들이 계곡을 떠날 수 있는지, 떠날 수 없다면 각자 상점이 있는 마을까지 최소한 얼마나 운전해야 하는지 알고 싶다. 어떤 도로가 막혔는지 아직 확실하지 않고 친구들도 계곡 곳곳의 서로 다른 마을에 살고 있으므로, 주어진 마을과 막힌 도로의 조합 Q개에 대해 이 질문에 답하는 프로그램을 작성해야 한다.
입력
첫째 줄에 정수 N, S, Q, E가 주어진다. N은 마을의 수, S (1 ≤ S ≤ N)는 상점의 수, Q는 프로그램에 주어지는 질의의 수, E (1 ≤ E ≤ N)는 계곡을 떠나기 위해 도달해야 하는 마을이다.
다음 N − 1개의 줄은 각각 세 정수 A, B, W로 이루어진다. 이는 마을 A와 B (1 ≤ A ≤ N, 1 ≤ B ≤ N)를 잇는 길이 W (1 ≤ W ≤ 109)의 도로가 있음을 뜻한다.
그다음 S개의 줄이 이어지며, 각 줄에는 정수 C 하나가 주어진다. 이는 마을 C (1 ≤ C ≤ N)에 상점이 있음을 뜻한다. 이 줄들은 모두 서로 다르다. 즉, 한 마을에 상점이 둘 이상 있는 경우는 없다.
마지막으로 Q개의 줄이 주어지며, 각 줄에는 두 정수 I와 R이 있다. 이는 입력에서 I번째 도로(1 ≤ I < N, 입력에 나열된 순서대로 번호가 매겨짐)를 더 이상 쓸 수 없으며, 마을 R (1 ≤ R ≤ N)에 있는 친구들이 계곡을 떠날 수 있는지, 떠날 수 없다면 상점이 있는 가장 가까운 마을까지의 거리가 얼마인지 알고 싶다는 뜻이다.
출력
출력은 Q개의 줄로 이루어진다. i번째 줄에는 입력의 i번째 질의에 대한 답이 들어간다. 더 정확히는, 계곡을 떠날 수 있으면 그 줄에 문자열 “escaped”(따옴표 제외)를 출력한다. 떠날 수 없으면 상점이 있는 가장 가까운 마을까지의 거리를 출력하고, 도달할 수 있는 상점이 더 이상 없으면 문자열 “oo”를 출력한다.