Cây nước (Water Tree)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Ban đầu mọi bể trên cây đều rỗng. Có ba thao tác: đổ đầy một đỉnh và toàn bộ cây con của nó; làm rỗng một đỉnh và toàn bộ tổ tiên; hỏi trạng thái đầy/rỗng của một đỉnh.

Dữ liệu vào

Dòng đầu chứa $n$, tiếp theo $n-1$ cạnh, rồi $q$ và $q$ thao tác type v, với $type\in\{1,2,3\}$.

Kết quả

Với mỗi thao tác loại 3, in 1 nếu đỉnh đầy nước, ngược lại in 0.

Subtask

Subtask 1 (20%)

• Kích thước cây và số thao tác không vượt 20.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• Kích thước cây và số thao tác không vượt 2000.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le5\cdot10^5$.

Ví dụ

Input

1
6
2 1
1 1
1 1
3 1
3 1
2 1

Output

1
1

Giải thích

Ví dụ được xử lý đúng theo thứ tự các thao tác. Các truy vấn chỉ quan sát trạng thái hiện tại sau toàn bộ cập nhật đứng trước chúng; kết quả in ra tương ứng với định nghĩa ở phần Đề bài.