한동이는 영업사원!

시간 제한1초메모리 제한128 MB

요약
트리가 주어질 때 1번 도시에서 시작해 주어진 순서대로 m개의 도시를 방문하며, 연속한 도시 사이의 거리를 모두 더한 값을 구한다.
난이도

보통10점 중 4점

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

문제

한동이는 여러 도시를 돌아다니며 열심히 일하는 영업사원이다. 예전에는 자기가 가고 싶은 도시만 골라서 다닐 수 있었지만, 시대가 바뀌어 이제는 그렇게 할 수 없다. 요즘 한동이는 회사에서 방문해야 할 도시의 목록을 받고, 그 목록에 적힌 순서 그대로 도시를 하나씩 방문해야 한다. 그런데 회사가 정해 준 방문 순서는 안타깝게도 전혀 최적화되어 있지 않다. 길을 떠나기 전에 한동이는 이 순서대로 모든 도시를 방문하는 데 걸리는 시간을 알고 싶어 한다.

포항 시내의 도시에는 11번부터 nn번까지 번호가 매겨져 있다. 한동이는 언제나 11번 도시인 포항시청에서 출발한다. 직접 도로로 이어진 두 도시 사이를 이동하는 데는 항상 11의 시간이 걸리며, 모든 도로는 양방향으로 통행할 수 있다. 11번 도시에서는 어떤 도시로도 갈 수 있고, 도로들은 어떤 사이클도 이루지 않는다. 즉 nn개의 도시와 n−1n-1개의 도로는 하나의 트리를 이룬다.

한동이는 11번 도시에서 출발하여 주어진 목록의 순서대로 도시를 방문한다. 두 도시 사이를 이동할 때는 항상 도로를 따라 최단 경로로 움직인다. 한동이가 목록에 있는 모든 도시를 순서대로 방문하는 데 필요한 최소 시간을 구하여라.

입력

첫째 줄에 포항에 있는 도시의 수 nn이 주어진다. (1≤n≤300001 \le n \le 30000)

다음 n−1n-1개의 줄에는 각 줄마다 두 정수 aa와 bb가 주어진다. 이는 aa번 도시와 bb번 도시가 도로로 직접 연결되어 있음을 뜻한다. (1≤a,b≤n1 \le a, b \le n, a≠ba \ne b)

그다음 줄에는 한동이가 방문해야 할 도시의 수 mm이 주어진다. (1≤m≤50001 \le m \le 5000)

이어지는 mm개의 줄에는 한동이가 방문해야 할 도시의 번호가 방문할 순서대로 한 줄에 하나씩 주어진다.

출력

한동이가 11번 도시에서 출발하여 주어진 순서대로 모든 도시를 방문하는 데 걸리는 최소 시간을 첫째 줄에 출력한다.

예제2

  1. 예제 1

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

    입력
    5
    1 2
    1 3
    1 4
    1 5
    4
    2
    3
    4
    5
    
    예상 출력
    7