Đất nước IOI, nơi JOI-kun sinh sống, có \(N\) thị trấn được đánh số từ \(1\) đến \(N\), cùng \(N-1\) con đường được đánh số từ \(1\) đến \(N-1\). Đường thứ \(j\) nối hai thị trấn \(U_j\) và \(V_j\) theo cả hai chiều. Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác qua các con đường.

Một cuộc hành trình sưu tập dấu sẽ được tổ chức. Mỗi thị trấn có một trạm đóng dấu; trạm ở thị trấn \(i\) được lắp đặt tại thời điểm \(T_i\).

JOI-kun quyết định tham gia. Cậu xuất phát từ một thị trấn ở thời điểm \(0\), với thể lực ban đầu \(D\). Khi ở thị trấn \(i\) tại thời điểm \(t\), cậu thực hiện các hành động sau:

1. Nếu trạm đóng dấu ở thị trấn hiện tại đã được lắp đặt, tức là \(T_i \le t\), cậu đóng dấu.
2. Cậu chọn kết thúc hành trình hoặc di chuyển sang thị trấn khác. Chỉ được chọn di chuyển nếu còn ít nhất \(1\) thể lực và có một thị trấn kề chưa từng ghé thăm.
3. Nếu chọn di chuyển, cậu chọn một thị trấn \(j\) chưa từng ghé thăm có đường nối trực tiếp với \(i\). Thể lực giảm \(1\) và cậu đến \(j\) tại thời điểm \(t+1\).
4. Nếu chọn kết thúc, hành trình thành công khi cậu đã đóng dấu ít nhất một lần; cậu nhận một món quà tại thị trấn kết thúc. Nếu chưa đóng dấu lần nào, hành trình thất bại.

Thời gian thực hiện mọi hành động ngoài việc đi giữa hai thị trấn là không đáng kể. JOI-kun không được đứng chờ tại một thị trấn.

Bạn là người tổ chức và phải chuẩn bị quà tại những thị trấn mà JOI-kun có thể kết thúc thành công. Do số quà có hạn, bạn muốn chuẩn bị quà ở ít thị trấn nhất có thể. Tuy nhiên, bạn chưa biết JOI-kun sẽ xuất phát từ đâu. Vì vậy, với mỗi thị trấn xuất phát \(s\) (\(1\le s\le N\)), hãy đếm số thị trấn \(g\) (\(1\le g\le N\)) sao cho tồn tại một hành trình thành công bắt đầu từ \(s\) và kết thúc tại \(g\).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N\), \(D\).
• Dòng thứ hai chứa \(N\) số nguyên \(T_1, T_2, \ldots, T_N\).
• \(N-1\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(U_j\), \(V_j\) mô tả một con đường.

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(s\) chứa số thị trấn cần chuẩn bị quà nếu JOI-kun xuất phát từ thị trấn \(s\).

Ràng buộc

• \(2 \le N \le 400000\).
• \(0 \le D \le N-1\).
• \(0 \le T_i \le N\).
• \(1 \le U_j < V_j \le N\).
• Đồ thị các thị trấn là liên thông.
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (3 điểm): \(D \le 1\).
• Nhóm 2 (7 điểm): \(N \le 3000\) và \((U_j, V_j) = (j, j + 1)\) với mọi \(1 \le j \le N - 1\).
• Nhóm 3 (10 điểm): \(N \le 3000\).
• Nhóm 4 (11 điểm): \((U_j, V_j) = (j, j + 1)\) với mọi \(1 \le j \le N - 1\).
• Nhóm 5 (41 điểm): \(D = N - 1\), \(N \le 150000\).
• Nhóm 6 (28 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 2
2 2 0 1 3
1 2
2 3
2 4
4 5

2
3
4
2
2

5 1
0 1 2 1 2
1 2
2 3
3 4
4 5

2
1
2
0
1

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

2
2
7
5
1
2
5

Nguồn

JOI 2025/2026 Final Stage, Competition 3, problem Collecting Stamps 5. Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.