Bedao Mini Contest 17 - PEACHTREE

Xem dạng PDF

Gửi bài giải


Điểm: 0,60 (OI)
Giới hạn thời gian: 3.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Tết nguyên đán Giáp Thìn (2024) đã đến rất gần, nhưng Quân vẫn chưa chuẩn bị được cây đào chơi tết. Ban lãnh đạo VNOI vừa đưa ra chỉ thị cho Hội đồng Bedao contest mua đào về chơi tết. Biết cây đào này là đào thất thốn (Đào tiến vua), lại được lai tạo cho ra hoa đa sắc, Quân lân la hỏi chuyện và đã được Sếp cho phép chọn ra một gốc đào nhỏ mang về nhà trưng.

Cây đào có thể coi như một đồ thị dạng cây với n đỉnh, gốc của cây đào sẽ là đỉnh với thứ tự là ~1~. Các đỉnh của cây sẽ được nối với nhau bằng các cành. Khi mới mua về, trên mỗi đỉnh của cây đào sẽ có không quá một bông hoa (Do người bán muốn duy trì dưỡng chất cho cây). Theo dòng thời gian, có thể có một số sự kiện diễn ra:

  • BLOOM ~x~ ~v~: Có một bông hoa đào màu ~x~ nở rộ trên đỉnh ~v~ của cây.

  • DISSOLVE ~x~ ~v~: Một bông hoa màu ~x~ trên đỉnh ~v~ đã bị héo và rụng.

Để chọn được cành hoa ưng ý về chơi tết, Quân sẽ xen một số câu hỏi vào giữa các "sự kiện":

  • TAKE ~u~ ~v~: Nếu Quân bẻ cành cây giữa hai đỉnh ~u~, ~v~ thì số màu hoa khác nhau mà quân mang về nhà là bao nhiêu ~?~

    Biết rằng khi bẻ cành cây, phần không chứa gốc sẽ là phần Quân được phép mang về, hay nói cách khác nếu như ~u~ là cha của ~v~ thì Quân sẽ mang cây con gốc ~v~ về nhà, ngược lại, Quân sẽ mang cây con gốc ~u~ về nhà. Dữ liệu đảm bảo có một cành nối giữa hai đỉnh ~u,\ v~ trên cây.

Bạn hãy giúp Quân trả lời các câu hỏi để anh có thể tìm được cành hoa ưng ý về trưng tết nhé.

Input

  • Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 5 \times 10^5)~ mô tả số sự kiện trong dòng thời gian.

  • Dòng thứ hai chứa ~n~ số nguyên ~a_1,\ a_2, \ldots,\ a_n~ ~(-1 \le a_i \le 10^6)~ với ~a_i~ là màu của bông hoa trên đỉnh ~i~ của cây (nếu ~a_i = -1~ thì trên đỉnh ~i~ không có bông hoa nào).

  • ~n - 1~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~u,\ v~ ~(1 \le u,\ v \le n,\ u \neq v)~ mô tả một cành của cây đào.

  • Dòng tiếp theo chứa một số nguyên dương ~q~ ~(1 \le q \le 5 \times 10^5)~ mô tả số sự kiện trong dòng thời gian.

  • ~q~ nhóm dòng cuối nhóm dòng gồm ~2~ dòng:

    • Dòng đầu tiên chứa một xâu ~s~ và hai số nguyên ~x,\ v~ ~(0 \le x \le 2 \times 10^6,\ 0 \le v \le 2 \times 10^6)~ mô tả một sự kiện.

      Lưu ý: Vì thời gian qua đi không trở lại, nên gọi ~\it{ans}~ là câu trả lời cho câu hỏi trước đó của Quân (Nếu chưa có câu hỏi nào thì ~\it{ans} = 0~), màu của bông hoa sẽ là ~x' = x~ xor ~\it{ans}~ và đỉnh mà hoa nở sẽ là ~v'~ = ~v~ xor ~\it{ans}~

      Dữ liệu đảm bảo ~0 \le x' \le 10^6~ và ~1 \le v' \le n~

    • Dòng thứ hai chứa xâu TAKE và hai số nguyên ~u,\ v~ ~(1 \le u,\ v \le n,\ u \neq v)~ mô tả mội câu hỏi của Quân.

Output

  • In ra ~q~ dòng, trên mỗi dòng in ra một số nguyên là đáp án cho câu hỏi tương ứng của Quân.

Subtask

  • ~20\%~ số test của bài với ~n,\ q \le 5000~

  • ~20\%~ số test khác của bài có màu của các bông hoa không giống nhau

  • ~20\%~ số test khác cùa bài với ~u,\ v~ giống nhau trong mọi câu hỏi

  • ~40\%~ số test còn lại không có điều kiện gì thêm

Sample Input 1

5
1 -1 3 -1 5
1 3
2 4
1 5
5 4
5
BLOOM 2 2
TAKE 4 5
DISSOLVE 2 2
TAKE 2 4
BLOOM 5 4
TAKE 1 3
DISSOLVE 5 5
TAKE 4 2
BLOOM 2 0
TAKE 1 5

Sample Output 1

1
1
0
1
2

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.