겁쟁이 조깅객

사진 제공 David Spencer

Lill-Jansskogen의 숲에는 조깅객들이 자주 이용하는 산책로망이 있다. 이 산책로들은 많은 사랑을 받아 왔으며, Royal Institute of Technology의 교수들이 특별히 선정하여 대학생들이 공부에서 잠시 벗어나 명석한 정신을 새롭게 할 수 있도록 했다. 이상하게도 이 산책로망은 실제로 트리를 이룬다. 산책로를 선정할 때 대학 교수들은 Lill-Jansskogen에서 발견한 산책로들의 집합으로 최소 신장 트리를 만들었다. 이는 “아름다운 Royal Institute of Technology의 환경에서 그래프 이론을 적용함으로써 컴퓨터 과학도들이 신체 활동에 참여하도록 장려하고 고무하기 위해서”였다.

안타깝게도 컴퓨터 과학도들은 그다지 용감하지 않다. 겨울이 다가오고 있으며, Stockholm시는 점점 더 어두워지고 있다. 최근 CSC (Community of Scared Cowards)의 프로그래머 무리가 밤에는 산책로망의 일부 구간이 너무 어둡다고 불평해 왔다. 몇몇 산책로는 가로등으로 밝혀져 있지만, 때로는 그것만으로 CSC에게 충분하지 않다. 그들은 자신들이 이용할 수도 있는 모든 산책로가 제대로 밝혀져 있기를 바란다!

교차로에 가로등을 설치하여 이 겁쟁이들을 만족시키는 임무가 주어졌다. 경제적인 이유로 모든 교차로에 가로등을 설치할 수는 없을 수도 있으므로, 조깅객들이 이용할 가능성이 있는 산책로에 인접한 두 교차로 중 적어도 하나에는 가로등이 있도록 보장하면 충분하다. 일부 교차로에는 이미 가로등이 있으며, 물론 그 가로등들을 계속 사용할 수 있다.

조깅객들이 정확히 어떤 산책로를 이용하는지는 모르지만, 조깅객들이 항상 대학 캠퍼스에서 출발하여 대학 캠퍼스에서 끝낸다는 것은 알고 있다. 또한 조깅객들은 다가오는 마라톤을 위해 훈련 중이므로, 항상 총합이 정확히 특정 거리인 $S$미터를 달린다. 조깅객은 정확히 $S$미터를 달려야 한다는 조건을 충족하기 위해 산책로 한가운데를 포함하여 언제든지 방향을 돌릴 수 있다.

과제

숲의 지도와 교수들이 만든 최소 신장 트리에 포함된 조깅 산책로들이 주어진다. 각 교차로 쌍 사이에는 정확히 하나의 경로가 있음이 보장되며, 경로란 서로 인접한 산책로들의 집합이다. 위의 제한을 지키는 한 조깅객들이 어떤 산책로를 이용하더라도 겁먹은 주자들을 만족시키기 위해 필요한 추가 가로등의 최소 개수를 구해야 한다.

입력은 교차로의 개수와 조깅객이 달리고자 하는 총 거리(미터)를 각각 나타내는 두 정수 $N$ ($2 \leq N \leq 50\,000$)와 $S$ ($1 \leq S \leq 10^4$)로 시작한다. 이어서 세 정수 $a$ ($1 \leq a \leq N$), $b$ ($1 \leq b \leq N$), $d$ ($1 \leq d \leq 100$)가 주어지는 $N-1$개의 줄이 따른다. 이는 교차로 $a$와 $b$ 사이에 길이가 $d$미터인 양방향 산책로가 있다는 뜻이다. 그다음 줄에는 이미 설치된 가로등의 개수를 나타내는 정수 하나 $L$ ($0 \leq L \leq N$)가 주어진다. 그다음 한 줄에 서로 다른 정수 $\ell_1, \dots, \ell_L$가 $L$개 주어지며, 이는 교차로 $\ell_1, \dots, \ell_L$에 이미 가로등이 설치되어 있다는 뜻이다. 대학 캠퍼스는 번호가 1인 교차로에 있다.

조깅객들의 요구 사항을 만족시키기 위해 추가로 설치해야 하는 가로등의 최소 개수를 나타내는 정수 하나를 출력한다.