병원 진료실 중심 찾기

문제

한 병원에는 번호가 1부터 N까지인 N개의 진료실이 있고, 복도 N-1개가 진료실들을 연결한다. 복도는 양방향이며 각 복도에는 걸어서 이동하는 데 걸리는 시간(초)이 정해져 있다. 어느 진료실에서든 다른 모든 진료실로 갈 수 있는 구조이다. 예약 시스템은 접수 창구를 진료실 한 곳에 설치하려 한다. 진료실 v에 창구를 설치했을 때의 불편도를, v에서 가장 멀리 있는 진료실까지의 이동 시간, 즉 v에서 다른 모든 진료실까지의 최단 이동 시간 중 최댓값으로 정의한다. 진료실이 하나뿐이면 불편도는 0이다. 시스템은 두 가지를 알고 싶어 한다. 첫째, 불편도가 가장 작은 진료실의 불편도와 그 진료실의 번호이다. 불편도가 가장 작은 진료실이 여럿이면 번호가 가장 작은 것을 고른다. 둘째, 불편도가 정수 L 이하인 진료실의 수이다. 이 두 값을 구하는 프로그램을 작성하시오. 이동 시간의 합은 32비트 정수 범위를 넘을 수 있다. 진료실의 수가 많아 모든 진료실에서 각각 탐색하면 시간 안에 끝나지 않는다.

입력

첫 줄에 진료실의 수 N과 정수 L이 공백으로 구분되어 주어진다. 이어지는 N-1개의 줄에 각각 복도가 잇는 두 진료실의 번호 u, v와 이동 시간 w가 주어진다. 1 ≤ N ≤ 200,000, 0 ≤ L ≤ 200,000,000,000,000, 1 ≤ u, v ≤ N, 1 ≤ w ≤ 1,000,000,000 이며 모든 값은 정수이다. 입력은 항상 트리를 이룬다.

출력

첫 줄에 '최소 불편도 진료실번호'를, 둘째 줄에 불편도가 L 이하인 진료실의 수를 출력한다.

5 8
1 2 3
2 3 4
2 4 2
4 5 6

6 4
2

1 0

0 1
1

3 5
1 2 5
1 3 5

5 1
1

출처: Devin.KR 자체 제작