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

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

경주

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

요약
트리와 시작점 및 끝점으로 허용된 정점 집합이 주어질 때, 양 끝점이 모두 허용된 정점인 정점 서로소 경로의 최대 개수를 구한다.
난이도

어려움10점 중 8점

유형
트리, 동적 계획법, DFS, 그리디
정답자
아직 제출이 없습니다

문제

선거가 다가오자 바이트타운(Bytetown) 시장은 지지율을 높이려고 육상 대회를 열기로 했다. 하지만 바이트타운에는 경기장이 없어서 모든 종목을 거리에서 진행해야 한다. 시장은 종목을 달리기 경주로만 한정하고, 경로(route) 배치를 도와달라고 부탁했다.

바이트타운에는 nn개의 교차로와 n−1n-1개의 거리(도로)가 있다. 이 거리들을 이용하면 임의의 두 교차로 사이를 오갈 수 있다. 즉, 교차로와 거리는 하나의 트리를 이룬다. 각 경로는 한 교차로에서 출발해 여러 개의 거리를 지나 다른 교차로에서 끝난다. 시장은 되도록 많은 종목을 동시에 열고 싶어 하므로, 경로의 개수를 최대로 만들어야 한다.

안전을 위해 서로 다른 두 경로는 어떤 교차로도, 어떤 거리도 공유할 수 없다. 또한 모든 교차로가 경주의 출발점이나 도착점이 될 수 있는 것은 아니다. 출발점과 도착점은 지정된 교차로들 중에서만 고를 수 있으며, 경로가 중간에 지나가기만 하는 교차로에는 이런 제약이 없다.

동시에 열 수 있는 경주(경로)의 최대 개수를 구하여라.

입력

첫째 줄에 교차로의 수 nn (1≤n≤1,000,0001 \le n \le 1{,}000{,}000)이 주어진다. 교차로는 11번부터 nn번까지 번호가 매겨져 있다.

다음 n−1n-1개의 줄에는 각 거리의 정보가 주어진다. 각 줄에는 그 거리의 양 끝 교차로 번호를 나타내는 두 정수 aa와 bb (1≤a,b≤n1 \le a, b \le n, a≠ba \ne b)가 공백으로 구분되어 주어진다.

그다음 줄(n+1n+1번째 줄)에는 경주의 출발점 또는 도착점이 될 수 있는 교차로의 수 mm (0≤m≤n0 \le m \le n)이 주어진다.

마지막 줄에는 그러한 교차로 mm개의 번호가 공백으로 구분되어 주어진다. 각 번호는 서로 다르며 모두 [1,n][1, n] 범위 안에 있다.

출력

바이트타운에서 동시에 열 수 있는 경주의 최대 개수를 정수 하나로 출력한다.

예제3

  1. 예제 1

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

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

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