USACO 2019 - Dec - Gold - Milk Visits
Xem dạng PDF
Nông dân John đang định xây ~N~ trang trại được nối bởi ~N - 1~ con đường, tạo thành một đồ thị cây (mọi trang trại tới được nhau, và không tồn tại chu trình). Trang trại ~i~ có một loại bò là ~T_{i}~.
Nông dân John có ~M~ người bạn thường đến thăm anh ấy. Trong chuyến thăm của người bạn thứ ~i~, nông dân John sẽ cùng bạn mình đi trên các con đường từ trang trại ~A_{i}~ đến trang trại ~B_{i}~ (có thể ~A_{i} = B_{i}~). Hơn nữa, họ có thể uống sữa của bất kì con bò nằm trên các trang trại dọc đường đi từ trang trại ~A_{i}~ đến trang trại ~B_{i}~. Tuy nhiên, bạn của nông dân John chỉ thích uống sữa từ một loại bò nhất định. Các bạn của nông dân John sẽ chỉ được thỏa mãn nếu như họ có thể uống sữa từ loại bò họ thích.
Hãy xác định liệu bạn của John có được thỏa mãn sau chuyến thăm.
Input
Dòng đầu tiên chứa hai số nguyên dương ~N~, ~M~ ~(1 \le N, M \le 10^5)~.
Dòng thứ hai chứa ~N~ số nguyên ~T_{1},T_{2},...,T_{N}~ là loại bò của mỗi trang trại ~(1 \le T_{i} \le N)~.
~N - 1~ dòng tiếp theo chứa 2 số nguyên ~X~ và ~Y~ phân biệt ~(1 \le X, Y \le N)~ thể hiện tồn tại 1 con đường nối trang trại ~X~ và ~Y~.
~M~ dòng tiếp theo, dòng thứ ~i~ chứa các số nguyên ~A_{i}, B_{i}~ và ~C_{i}~. Trong đó ~A_{i}~ và ~B_{i}~ là hai đầu chuyến thăm của người bạn thứ ~i~, ~C_{i}~ là loại bò mà người bạn thứ ~i~ thích ~(1 \le A_{i}, B_{i}, C_{i} \le N)~.
Output
- In ra xâu nhị phân có độ dài ~M~. Kí tự thứ ~i~ của xâu là ~1~ nếu người bạn thứ ~i~ được thỏa mãn, và ~0~ nếu ngược lại.
Sample Input 1
5 5
1 1 2 1 2
1 2
2 3
2 4
1 5
1 4 1
1 4 2
1 3 2
1 3 1
5 5 1
Sample Output 1
10110
Sample Input 2
6 4
1 2 3 3 3 3
1 2
2 3
3 4
2 5
5 6
4 6 1
4 6 2
4 6 3
4 6 4
Sample Output 2
0110
Giới hạn
- Test 1-2 chính là test ví dụ.
- Test 3 có ~N \le 10^3, M \le 2*10^3~.
- Các tests 4-7 có ~C_{i} \le 10~.
- Các test còn lại có giới hạn gốc.
Bình luận
Spoil thuật⚠️
Theo một gợi ý của tiền bối nào đó Yugi Hacker, mình đã AC bài này ✍️(◔◡◔)
orzz
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.