Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Trên web đọc dữ liệu từ bàn phím (stdin) và in ra màn hình (stdout).

Nguồn: Olympic truyền thống 30/4 lần XXVII – 2023, Tin học khối 10 – Câu 2.

Tâm rất yêu thích lập trình tạo phần mềm. Vào dịp rảnh rỗi Tâm đã thiết kế một phần mềm đơn giản. Màn hình phần mềm gồm ~N~ địa điểm (đánh số từ ~1~ đến ~N~), trong đó mỗi địa điểm có đặt một bóng đèn ở trạng thái sáng hoặc tắt. Có ~N - 1~ con đường một chiều nối trực tiếp giữa các cặp địa điểm. Mỗi lần Tâm chạm tay vào một địa điểm ~X_i~ bất kì trên màn hình thì sẽ có một robot xuất phát từ địa điểm ~X_i~ di chuyển theo các con đường một chiều, cuối cùng kết thúc ở địa điểm ~1~. Robot không thay đổi trạng thái đèn ở địa điểm ~X_i~ và địa điểm ~1~, các địa điểm còn lại robot đã đi qua thì đèn ở địa điểm đó sẽ thay đổi sang trạng thái ngược lại (sáng thành tắt, tắt thành sáng).

Yêu cầu: Hãy cho biết khi Tâm thực hiện ~K~ lần chạm tay (mỗi lần chạm tay vào một địa điểm) thì sau đó sẽ có tất cả bao nhiêu địa điểm có đèn sáng. Biết rằng robot xuất phát từ địa điểm bất kì luôn có thể di chuyển theo các con đường một chiều đến địa điểm ~1~.

Dữ liệu vào

• Dòng đầu tiên gồm 2 số nguyên dương ~N~ và ~K~ lần lượt là số địa điểm, số lần chạm tay ~(1 \le N, K \le 100000)~.
• Dòng thứ hai gồm ~N~ số nguyên cho biết trạng thái đèn ở ~N~ địa điểm, lần lượt theo thứ tự từ địa điểm ~1~ đến địa điểm ~N~. Trạng thái đèn tắt là ~0~, sáng là ~1~.
• Dòng thứ ~i~ trong ~N - 1~ dòng tiếp theo gồm hai số nguyên dương ~A_i~ và ~B_i~ ~(1 \le A_i, B_i \le N)~ cho biết có con đường một chiều nối trực tiếp từ địa điểm ~A_i~ đến ~B_i~.
• Dòng cuối cùng gồm ~K~ số nguyên dương, trong đó số nguyên thứ ~i~ là ~X_i~ ~(1 \le X_i \le N)~ cho biết địa điểm thứ ~i~ mà Tâm thực hiện chạm tay.

Kết quả

• Một số nguyên duy nhất là số địa điểm có đèn sáng sau ~K~ lần chạm tay.

Giới hạn

• ~1 \le N, K \le 100000~.
• 50% số test ứng với 50% số điểm có ~1 \le N, K \le 5000~.

Sample Input 1

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

Sample Output 1

3

Sample Input 2

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

Sample Output 2

2

Giải thích

Ví dụ 1: Tâm chạm tay 3 lần.

• Lần 1 ở địa điểm 4: robot đi qua các địa điểm 4, 2, 1 và thay đổi trạng thái đèn ở địa điểm 2. Kết quả trạng thái 5 đèn theo thứ tự lần lượt là: 1 1 0 0 0.
• Lần 2 ở địa điểm 5: robot đi qua các địa điểm 5, 4, 2, 1 và thay đổi trạng thái đèn ở địa điểm 4, 2. Kết quả trạng thái 5 đèn lần lượt là: 1 0 0 1 0.
• Lần 3 ở địa điểm 4: robot đi qua các địa điểm 4, 2, 1 và thay đổi trạng thái đèn ở địa điểm 2. Kết quả trạng thái 5 đèn lần lượt là: 1 1 0 1 0.

Sau 3 lần chạm tay, có 3 địa điểm có đèn sáng là địa điểm 1, 2 và 4.