23837번 - 구사과 시티

문제

구사과 시티는 N개의 정점으로 이루어진 트리로 나타낼 수 있다. 트리의 정점은 0부터 N-1까지 번호가 매겨져 있고, 0 ≤ i < N-1 을 만족하는 정점 i+1은 정점 A_i와 간선으로 연결되어 있다. 간선을 이동하고 한 정점에서 다른 정점으로 이동할 때는 1분이 필요하다.

구사과 시티의 시민들은 이동할 때 걸리는 시간을 줄이기 위해 도시에 텔레포트 장치를 설치하기로 했다. 텔레포트 장치는 동일하게 생긴 두 부스로 이루어져 있고, 각각은 정점에 있어야 한다. 한 부스로 들어가면 그 즉시 다른 부스로 나오게 된다. 두 부스를 같은 정점에 설치하는 것도 가능하다.

두 정점 사이의 거리는 한 정점에서 다른 정점으로 가기 위해 필요한 시간의 최솟값과 같다. N과 간선의 정보, 그리고 정수 X가 주어진다. D를 임의의 두 정점 사이의 거리 중 최댓값으로 정의했을 때, D가 X를 넘지 않는 텔레포트 장치 설치 방법의 수를 구해보자.

입력

첫째 줄에 두 정수 N과 X가 주어진다. 둘째 줄에는 N-1개의 정수 A_i가 주어진다.

출력

첫째 줄에 D가 X를 넘지 않는 텔레포트 장치 설치 방법의 수를 출력한다.

제한

• 2 ≤ N ≤ 2,000
• 0 ≤ X ≤ N
• 0 ≤ A_i ≤ i (0 ≤ i < N-1)

힌트