Color On Path
Xem dạng PDF
Gửi bài giải
Điểm:
0,25 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một cây có gốc bao gồm ~n~ nút. Các nút được đánh số ~1,2,... ,n~ và nút ~1~ là gốc của cây. Nút thứ ~i~ trên cây có giá trị là ~c_i~, được biết ~(1 \le c_i \le n)~.
Bạn có ~q~ truy vấn có dạng như sau:
- ~a,b,c~: Hỏi trên đường đi từ đỉnh ~a~ tới đỉnh ~b~, liệu có tồn tại đỉnh nào có màu bằng ~c~ hay không.
Input
- Dòng đầu tiên chứa hai số nguyên dương ~n,q~ ~(1 \le n,q \le 10^5)~
- Dòng thứ hai chứa ~n~ số nguyên ~c_1,c_2,...,c_n~ miêu tả màu của các đỉnh.
- ~n-1~ dòng sau, mỗi dòng chứa hai số nguyên ~u,v~ ~(1 \le u,v \le n)~ miêu tả cạnh ~(u,v)~.
- ~q~ dòng sau, dòng thứ ~i~ chứa ba số nguyên ~a,b,c~ miêu tả truy vấ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 truy vấn thứ ~i~ tồn tại đỉnh có màu là ~c~ tương ứng, ngược lại là ~0~.
Example
Sample Input
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
10110
Bình luận
https://oj.vnoi.info/problem/usaco19dg_milkvisits bài tương tự