문제
알고리즘 강의 자료를 온라인으로 공급하기 위해서 정올 네트워크사에서는 유능한 회사원 정택이를 파견하여 서버를 몇 대 설치하기로 했다.
당연히 서버를 조금 설치하는 게 좋겠지만, 이 네트워크라는 것이 통신망이 길면 길수록 속도가 자연스레 느려진다. 그래서 서버로부터 너무 멀리 있는 집에는 공급이 안 된다.
당연히 모든 집에 서버를 설치해야 할 텐데, 다행스럽게도 이미 연결된 네트워크망을 보니 알고리즘을 이해하고 있는 한컴 네트워크 사는 네트워크를 트리 모양으로 구성해 경제적으로 활용하고 있었다.
학생들의 컴퓨터를 데이터 전송용으로 사용할 수는 없으니 트리의 단말 노드는 항상 학생들의 집이다. 물론 예외적으로 메인 서버는 트리의 단말 노드에 있을 수도 있다.
메인 서버가 아닌 곳에는 그냥 데이터 전송용 서버만 있는데, 이러한 노드들 가운데 몇 곳을 골라 동영상 서버를 추가적으로 설치하려고 한다. 메인 서버와 동영상 서버는 모두 똑같이 거리가 K 이하에 있는 학생들에게 강의를 전송할 수 있다. 모든 학생들에게 강의를 제공하려면 몇 대의 서버가 추가적으로 필요할까?
입력
첫 행에는 100,000 이하의 네트워크의 노드의 수 N이 주어진다. 각 정점의 번호는 1부터 N까지 차례로 주어진다.
다음 행에는 메인 서버의 노드 번호와 K가 주어진다. K는 매우 클 수 있다.
다음 N-1개의 행에 걸쳐 각 간선의 양 끝 점의 번호가 주어진다.
출력
조건을 만족시키는 최소 추가 서버의 수를 출력한다.
예제
14
12 2
1 2
2 3
3 4
4 5
5 6
5 7
5 8
4 9
3 10
2 12
12 14
14 13
14 11
1
로그인해야 코드를 작성할 수 있어요.