Tuyến an toàn tới trạm dịch vụ

Bối cảnh và bài toán

Một khu vận hành được mô hình bằng cây có gốc tại nút 1. Một số nút nằm trong vùng cảnh báo. Các trạm dịch vụ đặt tại các lá. Một tuyến từ gốc tới trạm chỉ được chấp nhận nếu không xuất hiện quá m nút cảnh báo liên tiếp.

Yêu cầu

Đếm số trạm dịch vụ có tuyến đi từ gốc thỏa điều kiện an toàn.

Input

• Dòng 1 chứa n m.
• Dòng 2 chứa n giá trị 0/1 mô tả trạng thái cảnh báo của từng nút.
• n-1 dòng tiếp theo chứa các cạnh vô hướng u v của cây.

Output

In số lá có đường đi từ nút 1 thỏa giới hạn cảnh báo liên tiếp.

Ràng buộc

• 2 <= n <= 10^5
• 1 <= m <= n
• Đồ thị đầu vào là một cây.

Chấm điểm

Ví dụ 1

Input

7 1
1 1 0 0 0 0 1
1 2
1 3
2 4
2 5
3 6
3 7

Output

2

Giải thích. Hai lá có đường đi không vượt quá một nút cảnh báo liên tiếp.

Ví dụ 2

Input

3 0
0 1 0
1 2
1 3

Output

1

Giải thích. Nhánh tới nút 2 chứa cảnh báo nên bị loại; nút 3 hợp lệ.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces 580C – Kefa and Park.