Danil và công việc bán thời gian (Danil and a Part-time Job)

Nguồn: Codeforces

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

Đề bài

Mỗi đỉnh là một phòng có đèn bật hoặc tắt. Lệnh pow v đảo trạng thái mọi đèn trong cây con của $v$; lệnh get v đếm số đèn đang bật trong cây con.

Dữ liệu vào

Dòng đầu chứa $n$. Dòng hai chứa $p_2,\ldots,p_n$. Dòng ba chứa trạng thái đèn. Dòng bốn chứa $q$, tiếp theo là các lệnh pow v hoặc get v.

Kết quả

Với mỗi lệnh get, in số đèn đang bật trong cây con.

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\le2\cdot10^5$, trạng thái đèn là 0 hoặc 1.

Ví dụ

Input

1

0
8
pow 1
get 1
pow 1
get 1
pow 1
pow 1
get 1
get 1

Output

1
0
0
0

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.