406120: GYM102270 B Crush

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Crushtime limit per test1 secondmemory limit per test256 megabytesinputCRUSH.INPoutputCRUSH.OUT

B là một anh chàng chuyên tin đz, ngầu lòi. Anh chàng coder của chúng ta hiện đang crush một cô nàng chuyên Nga xinh xắn, hiền lành, C. Nhưng do khoảng cách địa lý giữa hai tòa nhà A1 và A2 nên B không thể nhìn thấy C mỗi giờ ra chơi.

Nhưng dựa vào tài năng "Hắc cơ" của mình, anh đã hack được camera của trường chỉ dựa vào chiếc điện thoại của mình. Nhưng anh không ngờ rằng ông mặt nhăn bảo vệ trường thật ra chính là trùm cuối trong đường dây gian lận thi cử.

Ông đã thiết kế mạng lưới camera rất tinh vi, là một mạng liên thông có N - 1 đường kết nối, không có chu trình và một số camera cần có mật khẩu mới có thể truy cập. Tất nhiên B vẫn phá được mật khẩu nhưng sẽ bị mất 1 năng lượng pin điện thoại. Bạn hãy giúp B đếm số cách sử dụng đúng K năng lượng để truy cập các camera để anh có thể triệt phá đường dây và chinh phục crush của mình nhé.

Input

Dòng đầu tiên chứa 2 số nguyên N, K lần lượt là số camera và số năng lượng pin.

Dòng thứ hai chứa N số nguyên là 0 / 1 biểu thị camera thứ i có mật khẩu hay không.

N - 1 dòng tiếp theo chứa 2 số nguyên u, v biểu thị có đường kết nối giữa camera u và camera v.

Output

In ra một dòng duy nhất là kết quả bài toán.

Scoring

1 ≤ N ≤ 50000.

1 ≤ K ≤ 100.

20% số test với N ≤ 25.

30% số test với N ≤ 1000.

20% số test với K ≤ 10.

ExamplesInput
5 2
0 1 0 1 1
1 2
1 3
1 4
2 5
Output
5
Input
3 1
1 0 1
1 2
1 3
Output
3
Input
3 0
1 1 0
1 2
2 3
Output
1
Note

Giải thích test 1: {1, 2, 3}, {2, 5}, {1, 3, 4}, {1, 2, 5}, {1, 2, 4}.

Giải thích test 2: {1}, {3}, {1, 2}.

Giải thích test 3: {}. (tập rỗng)

加入题单

上一题 下一题 算法标签: