Cây năm mới (New Year Tree)

Nguồn: Codeforces

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

Đề bài

Mỗi đỉnh có một màu từ 1 đến 60. Hỗ trợ tô toàn bộ cây con của một đỉnh bằng một màu và đếm số màu khác nhau trong cây con.

Dữ liệu vào

Dòng đầu chứa $n,m$, dòng hai chứa màu ban đầu, tiếp theo $n-1$ cạnh, rồi $m$ truy vấn 1 v c hoặc 2 v.

Kết quả

Với mỗi truy vấn loại 2, in số màu khác nhau 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,m\le4\cdot10^5$, $1\le c_i,c\le60$.

Ví dụ

Input

1 15
43
2 1
2 1
2 1
2 1
2 1
1 1 13
2 1
2 1
2 1
2 1
2 1
1 1 34
2 1
2 1
2 1

Output

1
1
1
1
1
1
1
1
1
1
1
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.