DHBB 2024 - CBH - 11 - Tập hợp đẹp
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho một cây có ~n~ đỉnh, đỉnh ~1~ là gốc. Mỗi đỉnh trên đều được tô màu, đỉnh thứ ~i~ được tô bởi màu ~a_i~. Một tập hợp các đỉnh trên được gọi là đẹp nếu có hơn một nửa số đỉnh trong tập được tô bởi cùng một màu.
Có ~m~ truy vấn, mỗi truy vấn thuộc một trong các dạng sau:
Truy vấn dạng: ~1\ u~, truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm trong cây con gốc ~u~ có phải là một tập đẹp hay không;
Truy vấn dạng: ~2\ u~, truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm ngoài cây con gốc ~u~ có phải là một tập đẹp hay không;
Truy vấn dạng ~3\ u\ v~, truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm trên đường đi từ ~u~ tới ~v~ (tính cả ~u~ và ~v~) có phải là một tập đẹp hay không.
Input
Dòng đầu tiên chứa ~2~ số nguyên dương ~n, m~ lần lượt là số đỉnh trên cây và số truy vấn;
Dòng thứ ~2~ chứa ~n~ số nguyên dương, số thứ ~i~ là ~a_i~ ~(1 \le a_i \le n)~;
Mỗi dòng trong số ~n - 1~ dòng tiếp theo chứa ~2~ số nguyên dương ~u, v~ tương ứng với có cạnh nối từ đỉnh ~u~ tới đỉnh ~v~ trên cây;
~m~ dòng tiếp theo là các loại truy vấn.
Output
In ra ~m~ dòng là kết quả của ~m~ truy vấn, nếu tập các đỉnh của truy vấn đang xét có quá nửa được tô cùng một màu thì in ra màu đó, ngược lại in ra -1.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~25\%~ | ~n, m \le 2000~ |
| 2 | ~25\%~ | Mỗi đỉnh có tối đa ~2~ cạnh nối trực tiếp |
| 3 | ~25\%~ | ~n, m \le 50000~ và không có truy vấn loại ~3~ |
| 4 | ~25\%~ | ~n, m \le 5000~ |
Sample Input 1
8 5
2 3 3 1 2 1 3 1
1 2
1 3
2 4
2 5
3 7
5 6
6 8
1 2
3 4 6
2 6
2 5
3 1 5
Sample Output 1
1
-1
-1
3
2
Bình luận