Độ khó: Khó (4/4 điểm)

🎓 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

Mùa nước nổi về trên một vùng đồng bằng có ~N~ xã, đánh số từ ~1~ đến ~N~, nối với nhau bởi ~M~ con đường đất hai chiều. Con đường thứ ~i~ nối hai xã ~u_i, v_i~ và có cao độ ~h_i~. Khi mực nước là ~x~, những con đường có cao độ ~h_i \ge x~ vẫn còn đi được, những con đường có ~h_i < x~ thì bị ngập.

Mỗi xã nổi tiếng với đúng một loại đặc sản, xã thứ ~i~ có đặc sản loại ~c_i~ (nhiều xã có thể có cùng loại đặc sản).

Thầy Sơn muốn đi thu mua đặc sản để làm quà cho học trò. Thầy có ~Q~ câu hỏi, mỗi câu hỏi dạng: "Nếu thầy đang ở xã ~v~ và mực nước là ~x~, thì bằng cách chỉ đi trên các con đường chưa bị ngập, thầy có thể thu mua được bao nhiêu loại đặc sản khác nhau?" (kể cả đặc sản của chính xã ~v~; thầy được đi qua một xã hay một con đường nhiều lần).

Để tránh việc dự đoán trước, các câu hỏi có thể được mã hóa: tham số ~T~ cho biết điều này.

• Nếu ~T = 0~: câu hỏi thứ ~j~ cho trực tiếp hai số ~v, x~.
• Nếu ~T = 1~: câu hỏi thứ ~j~ cho hai số ~a, b~, khi đó ~v = a \oplus last~ và ~x = b \oplus last~, trong đó ~\oplus~ là phép XOR bit, ~last~ là đáp án của câu hỏi ngay trước đó (với câu hỏi đầu tiên, ~last = 0~).

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên ~N, M, Q, T~ ~(1 \le N \le 10^5;\ 0 \le M \le 2 \times 10^5;\ 1 \le Q \le 10^5;\ T \in \{0, 1\})~.
• Dòng thứ hai chứa ~N~ số nguyên ~c_1, c_2, \dots, c_N~ ~(1 \le c_i \le N)~.
• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, h_i~ ~(1 \le u_i, v_i \le N;\ u_i \ne v_i;\ 1 \le h_i \le 10^9)~. Giữa hai xã có thể có nhiều con đường.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả một câu hỏi như trên. Dữ liệu đảm bảo sau khi giải mã luôn có ~1 \le v \le N~ và ~1 \le x \le 10^9~.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~j~ là đáp án của câu hỏi thứ ~j~.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N, M, Q \le 2000~.
• Subtask 2 (~30\%~ số điểm): ~T = 0~.
• Subtask 3 (~50\%~ số điểm): ~T = 1~, không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây.

Sample Input 1

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

Sample Output 1

3
2
1
3

Sample Input 2

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

Sample Output 2

3
2
1
3

Giải thích

• Ví dụ 1 (đặc sản loại ~1, 2, 3~ lần lượt là lúa, cá, sen):
  • Câu ~1~: mực nước ~4~, từ xã ~1~ đi được các xã ~1, 2, 3, 4~ (đường ~2 - 3~ cao độ ~3~ và đường ~4 - 5~ cao độ ~2~ đã ngập) nên mua được ~3~ loại.
  • Câu ~2~: mực nước ~3~, từ xã ~5~ chỉ đi được xã ~6~, mua được ~2~ loại.
  • Câu ~3~: mực nước ~8~, mọi đường đều ngập, chỉ mua được đặc sản của xã ~4~.
  • Câu ~4~: mực nước ~2~, đi được tất cả các xã, mua được ~3~ loại.
• Ví dụ 2 là ví dụ 1 sau khi mã hóa. Chẳng hạn câu thứ hai cho ~a = 6, b = 0~, đáp án câu trước là ~3~ nên ~v = 6 \oplus 3 = 5~, ~x = 0 \oplus 3 = 3~. Lưu ý các số ~a, b~ trong dữ liệu có thể nằm ngoài đoạn ~[1, N]~ hoặc bằng ~0~.

Nguồn: Đề tự luyện HSG Tin học quốc gia do thầy Nguyễn Việt Nam Sơn biên soạn (đề tự soạn).