아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

나무 위의 다람쥐

면접 대비

시간 제한4초메모리 제한1024 MB

요약
1번 노드를 루트로 하는 트리에서 도토리가 있는 모든 노드를 방문하고 1번으로 돌아오는 최단 왕복 거리를 구한다.
난이도

보통10점 중 5점

유형
트리, DFS, 그래프, 그리디
정답자
아직 제출이 없습니다

문제

다람쥐가 NN개의 노드와 N−1N-1개의 간선으로 이루어진 나무에 살고 있다. 각 간선의 길이는 1이며 두 노드를 연결한다. 다람쥐는 몇몇 노드에 도토리를 숨겨 두었고, 이제 그것들을 모으려고 한다. 다람쥐가 1번 노드(나무의 뿌리)에서 출발할 때, 모든 도토리를 가져와 다시 1번 노드로 돌아오는 데 걸리는 최단 거리는 얼마인가? 다람쥐는 도토리를 여러 개 동시에 나를 수 있다.

모든 노드 쌍 사이를 간선을 따라 이동할 수 있다.

입력

첫째 줄에 두 정수 NN과 KK가 주어진다. (1≤K≤N≤100 0001 \le K \le N \le 100\,000) NN은 나무의 노드 수, KK는 도토리가 있는 노드의 수이다. 둘째 줄에 KK개의 서로 다른 정수가 주어지며, 이는 다람쥐가 도토리를 숨겨 둔 노드이다. 노드 번호는 1부터 NN까지이다. 이어서 N−1N-1개의 줄이 주어진다. 각 줄에는 두 정수 1≤a,b≤N1 \le a, b \le N이 주어지며, 이는 노드 aa와 노드 bb 사이에 간선이 있음을 뜻한다.

출력

모든 도토리를 가져오는 데 다람쥐가 이동해야 하는 최단 거리를 정수로 출력한다.

예제2

  1. 예제 1

    입력
    5 2
    4 5
    1 2
    2 3
    2 4
    1 5
    
    예상 출력
    6
    
  2. 예제 2

    입력
    10 4
    5 4 8 6
    2 7
    1 2
    4 2
    2 5
    5 3
    5 10
    6 7
    8 4
    9 4
    
    예상 출력
    12