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

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

겁 많은 조깅 동호회

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

요약
1번 교차로에서 출발해 정해진 거리를 뛰고 돌아올 때 지날 수 있는 모든 구간에 가로등이 닿도록 추가 가로등을 가장 적게 배치합니다.
난이도

보통10점 중 6점

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

문제

숲에 조깅용 산책로가 놓여 있다. 교차점은 NN개이고 산책로는 N−1N-1개이며, 어느 두 교차점 사이에도 산책로를 따라가는 경로가 정확히 하나 있다. 즉 산책로 전체가 하나의 트리를 이룬다.

조깅하는 사람은 모두 1번 교차점에서 출발해 정확히 SS미터를 달린 뒤 다시 1번 교차점으로 돌아온다. 달리는 도중 교차점이 아닌 산책로 한가운데에서도 방향을 바꿀 수 있고, 원하는 만큼 여러 번 바꿔도 된다. 누가 어느 경로로 달릴지는 알 수 없으므로, 이 조건을 만족하는 경로는 모두 실제로 쓰일 수 있다고 본다. 산책로의 일부만 밟고 되돌아온 경우에도 그 산책로를 이용한 것으로 친다.

밤에는 숲이 어둡다. 사람들은 자기가 지날 수 있는 산책로가 전부 밝기를 원한다. 산책로는 양 끝 교차점 중 적어도 한 곳에 가로등이 있으면 밝다. 이미 가로등이 설치된 교차점이 LL개 있고, 그 가로등은 그대로 쓴다.

쓰일 수 있는 산책로가 모두 밝아지도록 교차점에 가로등을 추가로 설치하려고 한다. 추가로 설치해야 하는 가로등의 최소 개수를 구하시오.

입력

첫 줄에 교차점의 개수 NN과 달리는 거리 SS가 주어진다. (2≤N≤500002 \le N \le 50000, 1≤S≤1041 \le S \le 10^4)

다음 N−1N-1개의 줄에는 각각 세 정수 aa, bb, dd가 주어진다. 교차점 aa와 bb를 잇는 길이 dd미터의 양방향 산책로가 있다는 뜻이다. (1≤a,b≤N1 \le a, b \le N, 1≤d≤1001 \le d \le 100)

다음 줄에 이미 가로등이 설치된 교차점의 개수 LL이 주어진다. (0≤L≤N0 \le L \le N)

그 다음 줄에 가로등이 설치된 교차점 번호 LL개가 공백으로 구분되어 주어진다. 번호는 모두 서로 다르다. LL이 00이면 이 줄은 비어 있다.

출력

추가로 설치해야 하는 가로등의 최소 개수를 한 줄에 출력한다.

예제3

  1. 예제 1

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

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

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