시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 128 MB | 156 | 31 | 24 | 17.778% |
한 달 가까이 구사과의 이상한 말들을 받아주느라 너무나 힘들었던 캇카흐는, 이제 대담한 복수를 하려고 합니다. 그 복수는 아니나 다를까, 멕카시나의 걸작, 후르츠 치킨을 구사과의 집으로 주문하는 것이죠!
구사과가 사는 곳은 매우 특이한 구조를 가지고 있습니다. 이 곳은 N개의 도시와 (N-1)개의 양방향 도로로 이루어져 있으며, 모든 도시 쌍 간에 그 두 도시를 잇는 경로가 존재합니다. 동쪽에 있는 도시들에는 멕카시나 가게들이 있고, 서쪽에 있는 도시들에는 구사과의 집들(맞아요, 구사과는 집이 여러 채 있는 부자에요!)이 있습니다. 물론 멕카시나도, 구사과의 집도 없는 도시도 있습니다.
그리고 이 곳에는 한 가지 더 특이한 점이 있습니다. 멕카시나가 있는 도시에서 구사과의 집으로 향하는 모든 경로는 어떤 특정한 도로를 지나도록 되어있습니다. 그 도로가 잇는 두 도시에는 멕카시나도, 구사과의 집도 없습니다.
캇카흐는 각 가게의 배달원들에게 연락하여, 그들이 어떻게 움직여야 하는지를 명령하려고 합니다. 구사과에게 들키지 않기 위해, 한 도로에 두 명 이상의 배달원(즉 둘 이상의 후르츠 치킨)이 동시에 있어서는 안 됩니다. 하지만 한 도시에 여러 명의 배달원이 대기하는 것은 가능합니다. 각각의 배달원들은 도로가 겹치지만 않는다면 동시에 이동이 가능합니다. 모든 도로를 지나는 데에는 1만큼의 시간이 걸립니다.
구사과에게 최대한 큰 정신적인 타격을 주기 위해서, 캇카흐는 후르츠 치킨이 서로 다른 구사과의 집으로 배달되기를 원합니다. 즉 어떤 두 치킨이 같은 집으로 배달되어서는 안 됩니다.
결전의 날이 왔습니다. 캇카흐는 모든 멕카시나 가게에 전화를 걸어, 오늘 영업하는 멕카시나 가게의 목록을 알아냈습니다. 캇카흐는 모든 후르츠 치킨이 배달되는 데에 필요한 시간을 최소화하고자 합니다. 구사과의 동네의 구조를 바탕으로, 치킨이 모두 배달되는 최소 시간을 구해주세요!
입력의 첫 번째 줄에는 도시의 수 N, 멕카시나의 가게의 수 W, 그리고 구사과의 집의 수 Z가 주어집니다. (1 ≤ N, W, Z ≤ 106) 도시는 1부터 N까지의 번호가 붙어있으며, 멕카시나 가게가 있는 도시는 1번부터 W번까지이고, 구사과의 집이 있는 도시는 (N-Z+1)번부터 N번까지입니다.
그 뒤의 (N-1)개의 줄에는 구사과의 동네의 구조에 대한 설명이 주어집니다. 각각의 줄에는 1 이상 N 이하의 정수 a, b가 주어집니다. 이는 a번 도시와 b번 도시를 잇는 도로가 있다는 것을 나타냅니다.
그 다음 줄은 오늘 영업중인 멕카시나 가게의 수를 나타내는 1 이상 W 이하의 정수 P (1 ≤ p ≤ min(W, Z))가 주어집니다. 다음 줄에는 1 이상 W 이하의 서로 다른 P개의 정수가 주어집니다. 각각의 정수는 오늘 영업하는 멕카시나 가게가 있는 도시의 번호를 나타냅니다.
첫 번째 줄에 모든 후르츠 치킨이 배달되는 데에 필요한 최소 시간을 출력하세요.
9 2 3 1 3 2 3 4 3 4 5 4 6 7 4 5 8 9 6 2 1 2
4
화살표는 치킨의 배달 과정을 나타냅니다. 제자리로 돌아오는 화살표는 배달원이 도로를 이용하기 위해 1의 시간만큼 기다렸음을 나타냅니다.