디미고에는 감나무가 한 그루 있다.
감나무는 루트가 번 노드인 트리이며, 모든 리프 노드에는 감이 개씩 열린다.
감을 좋아하는 ARUBA는 자신이 딸 수 있는 모든 감을 따고자 한다.
어떤 노드를 기준으로 감 따기를 수행하면, 그 노드를 루트로 하는 서브트리에서 다음 조건을 만족하는 모든 감을 딴다.
감 따기를 시작한 노드부터의 거리가 ARUBA의 키 이하이다.처음에 ARUBA는 번 노드에서 감 따기를 한 번 수행한다.
이후 ARUBA는 최대 한 번, 나무를 타고 올라가 트리의 원하는 노드 로 이동할 수 있다. 이동한 뒤에는 를 기준으로 를 한 번 더 수행한다.
감 따기같은 감은 여러 번 딸 수 없다.
감나무의 구조(트리)와 가 주어질 때, ARUBA가 딸 수 있는 감의 최대 개수를 구하는 프로그램을 작성하여라.
첫 번째 줄에 감나무의 노드 개수 과 ARUBA의 키 가 공백으로 구분되어 주어진다.
두 번째 줄부터 개의 줄에 걸쳐 각 줄에 간선으로 연결된 두 노드의 번호 , 와 해당 간선의 길이 가 공백으로 구분되어 주어진다.
모든 부모-자식 관계에 대하여 부모 노드의 번호가 자식 노드의 번호보다 작다.
첫 번째 줄에 ARUBA가 딸 수 있는 감의 최대 개수를 출력한다.