트리 위에서 뛰기

시간 제한4초메모리 제한512 MB

요약

트리와 정수 d가 주어질 때, 간선 d개 거리에 있는 정점끼리 이동으로 이어지는 정점 묶음의 개수를 구합니다.

난이도: 보통10점 중 7점
유형: 트리, 유니온 파인드, DFS
정답자: 아직 제출이 없습니다

문제

정점이 $n$ 개인 트리가 주어진다. 현재 정점이 $v$ 에 있다고 하자. 한 번의 이동에서 $v$ 와 $u$ 사이의 최단 경로에 있는 간선이 정확히 $d$ 개인, $v$ 와 다른 임의의 정점 $u$ 로 이동할 수 있다. 0번 이상의 이동으로 $v$ 에서 $u$ 로 갈 수 있으면 $u$ 는 $v$ 에서 도달 가능하다.

모든 정점은 도달 클래스로 나눌 수 있다. 도달 클래스는 정점 집합 $C$ 로서, $C$ 에 속한 임의의 정점이 $C$ 의 다른 모든 정점에서 도달 가능하고, $C$ 밖의 정점은 $C$ 의 어떤 정점에서도 도달할 수 없는 집합이다. 주어진 트리에 도달 클래스가 몇 개 있는지 구하라.

입력

첫 줄에 공백으로 구분된 두 정수 $n$ 과 $d$ 가 주어진다 ( $1 \leq n \leq 10^6$ , $0 \leq d \leq n$ ).

이후 $n - 1$ 개의 줄에 트리의 간선이 주어진다. 각 줄에는 간선으로 연결된 두 정점의 번호가 공백으로 구분되어 주어진다. 정점 번호는 1부터 시작한다.

출력

도달 클래스의 개수를 정수 하나로 출력한다.

예제1

예제 1
입력
```
4 2
1 2
2 3
3 4
```
예상 출력
```
2
```