시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 1024 MB116413745.679%

문제

안즈는 사탕나무를 생일선물로 받았다.

사탕나무는 \(N\)개의 사탕을 트리 형태로 이은 것을 말한다. 각 사탕은 길이가 1인 간선으로 연결되어있고, 임의의 두 사탕 사이의 최단 경로는 유일하다.

안즈는 이 사탕나무에서 기준이 되는 사탕을 하나 골라, 그 사탕과의 최단거리가 \(K\)이하인 모든 사탕을 다 먹어버리려고 한다!

그런데 안즈는 문득 기준으로 어떤 사탕을 골라야 사탕을 가장 많이 먹을 수 있을지 궁금해졌다.

하지만 그 순간 안즈는 매우 귀찮아졌기 때문에, 여러분에게 해결을 부탁했다.

입력

첫째 줄에 \(N\)과 \(K\)가 주어진다.

이어서 \(N\)-1개의 줄에, 사탕나무의 간선을 이루는 두 사탕 번호 \(u\), \(v\)가 공백으로 구분되어 주어진다.

주어지는 입력은 트리임이 보장된다.

출력

안즈가 먹을 수 있는 최대 사탕 개수를 출력한다.

제한

  • 3 ≤ \(N\) ≤ 105
  • 1 ≤ \(K\) ≤ 20
  • 1 ≤ \(u\), \(v\) ≤ \(N\), \(u \ne v\)

예제 입력 1

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

예제 출력 1

5


 

기준이 되는 사탕을 3번 사탕으로 정하면 총 5개의 사탕을 먹을 수 있다.

출처

University > 인하대학교 > 2021 인하대학교 프로그래밍 경진대회(IUPC) J번