나무 위의 다람쥐
면접 대비시간 제한4초메모리 제한1024 MB
1번 노드를 루트로 하는 트리에서 도토리가 있는 모든 노드를 방문하고 1번으로 돌아오는 최단 왕복 거리를 구한다.
문제
다람쥐가 개의 노드와 개의 간선으로 이루어진 나무에 살고 있다. 각 간선의 길이는 1이며 두 노드를 연결한다. 다람쥐는 몇몇 노드에 도토리를 숨겨 두었고, 이제 그것들을 모으려고 한다. 다람쥐가 1번 노드(나무의 뿌리)에서 출발할 때, 모든 도토리를 가져와 다시 1번 노드로 돌아오는 데 걸리는 최단 거리는 얼마인가? 다람쥐는 도토리를 여러 개 동시에 나를 수 있다.
모든 노드 쌍 사이를 간선을 따라 이동할 수 있다.
입력
첫째 줄에 두 정수 과 가 주어진다. () 은 나무의 노드 수, 는 도토리가 있는 노드의 수이다. 둘째 줄에 개의 서로 다른 정수가 주어지며, 이는 다람쥐가 도토리를 숨겨 둔 노드이다. 노드 번호는 1부터 까지이다. 이어서 개의 줄이 주어진다. 각 줄에는 두 정수 이 주어지며, 이는 노드 와 노드 사이에 간선이 있음을 뜻한다.
출력
모든 도토리를 가져오는 데 다람쥐가 이동해야 하는 최단 거리를 정수로 출력한다.