Một con mèo sống trên một cây có \(N\) đỉnh. Nó sẽ phân định lãnh thổ bằng cách “đánh dấu” một số đỉnh của cây. Khoảng cách giữa hai đỉnh được đánh dấu bất kỳ phải ít nhất là \(D\). Hãy tìm số đỉnh lớn nhất mà con mèo có thể đánh dấu.

Ảnh: Just a kitten in a tree, Zoe Shuttleworth, qua Flickr; CC BY-2.0.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(D\). Đỉnh \(0\) là gốc của cây.

Tiếp theo là \(N-1\) dòng. Dòng thứ \(i\), với \(1 \le i \le N-1\), chứa một số nguyên \(x_i\) thỏa mãn \(0 \le x_i < i\), cho biết đỉnh \(x_i\) được nối với đỉnh \(i\).

Dữ liệu ra

In ra một số nguyên: số đỉnh lớn nhất có thể được đánh dấu.

Ràng buộc

• \(1 \le N, D \le 2 \cdot 10^5\).
• \(0 \le x_i < i\) với mọi \(1 \le i \le N-1\).

Phân nhóm

Bạn chỉ nhận được điểm của một nhóm khi vượt qua tất cả các test trong nhóm đó. Tổng điểm là tổng điểm của các nhóm.

• Nhóm 1 (11 điểm): \(N \le 18\).
• Nhóm 2 (40 điểm): \(N \le 1\,500\).
• Nhóm 3 (49 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 3
0
0
1

2

3 1000
0
0

1

Nguồn

Baltic Olympiad in Informatics 2017, ngày thi thứ 2.