Tuyết đã phủ xuống trang trại, và cũng như vào đầu mỗi mùa đông, Bessie đang xây một cô bò tuyết! Phần lớn thời gian, Bessie cố gắng làm cho tác phẩm điêu khắc giống bò thật nhất có thể. Tuy nhiên, năm nay với cảm hứng nghệ thuật, cô quyết định đi theo một hướng trừu tượng hơn và xây tác phẩm điêu khắc theo hình một cái cây, gồm \(N\) quả cầu tuyết (\(1 \leq N \leq 10^5\)) được nối bằng \(N-1\) nhánh, mỗi nhánh nối một cặp quả cầu tuyết sao cho giữa mọi cặp quả cầu tuyết đều có một đường đi duy nhất.

Bessie đã gắn một chiếc mũi lên một trong các quả cầu tuyết, vì vậy nó biểu thị đầu của cô bò tuyết trừu tượng. Cô đánh số quả cầu này là 1. Để tác phẩm bắt mắt hơn, cô dự định nhuộm một số quả cầu tuyết bằng các màu khác nhau theo phong cách nghệ thuật: đổ thuốc nhuộm màu vào những thùng sữa cũ rồi hắt chúng lên tác phẩm. Các màu được nhận diện bằng những số nguyên trong phạm vi \(1 \ldots 10^5\), và Bessie có nguồn cung không giới hạn các xô thuốc nhuộm cho mọi màu có thể có.

Khi Bessie hắt một xô thuốc nhuộm lên một quả cầu tuyết, tất cả các quả cầu tuyết trong cây con của nó cũng bị hắt cùng màu thuốc nhuộm (quả cầu tuyết \(y\) nằm trong cây con của quả cầu tuyết \(x\) nếu \(x\) nằm trên đường đi từ \(y\) đến quả cầu tuyết làm đầu). Bằng cách hắt từng màu hết sức cẩn thận, Bessie đảm bảo rằng tất cả những màu từng được hắt lên một quả cầu tuyết vẫn sẽ nhìn thấy được. Ví dụ, nếu một quả cầu tuyết đã có các màu \([1,2,3]\) và Bessie hắt màu \(4\) lên nó, sau đó quả cầu tuyết sẽ có các màu \([1,2,3,4]\).

Sau khi hắt màu lên các quả cầu tuyết một số lần, Bessie cũng có thể muốn biết một phần của cô bò tuyết có bao nhiêu màu sắc. "Độ sặc sỡ" của một quả cầu tuyết \(x\) bằng số màu phân biệt \(c\) mà quả cầu tuyết \(x\) được nhuộm màu \(c\). Nếu Bessie hỏi bạn về quả cầu tuyết \(x\), bạn phải trả lời tổng độ sặc sỡ của tất cả các quả cầu tuyết trong cây con của \(x\).

Hãy giúp Bessie tìm độ sặc sỡ của cô bò tuyết tại một số thời điểm nhất định.

Phân nhóm

\(Q\) được định nghĩa bên dưới.

• Các test 2–3 thỏa mãn \(N \leq 10^2\), \(Q \leq 2\cdot 10^2\).
• Các test 4–6 thỏa mãn \(N \leq 10^3\), \(Q \leq 2\cdot 10^3\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và số truy vấn \(Q\) (\(1 \leq Q \leq 10^5\)).

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\), cách nhau bởi dấu cách, mô tả một nhánh nối các quả cầu tuyết \(a\) và \(b\) (\(1 \leq a,b \leq N\)).

Cuối cùng, mỗi dòng trong \(Q\) dòng cuối chứa một truy vấn. Một truy vấn có dạng

1 x c

cho biết Bessie hắt một xô nước ép màu \(c\) lên quả cầu tuyết \(x\), tô màu tất cả các quả cầu tuyết trong cây con của \(x\). Một dòng có dạng

2 x

là truy vấn tổng độ sặc sỡ của tất cả các quả cầu tuyết trong cây con của \(x\). Tất nhiên, \(1 \leq x \leq N\) và \(1 \leq c \leq 10^5\).

Dữ liệu ra

Với mỗi truy vấn loại 2, in tổng độ sặc sỡ trong cây con tương ứng.

Lưu ý rằng bạn nên sử dụng số nguyên 64 bit để tránh tràn số.

Ví dụ

5 18
1 2
1 3
3 4
3 5
1 4 1
2 1
2 2
2 3
2 4
2 5
1 5 1
2 1
2 2
2 3
2 4
2 5
1 1 1
2 1
2 2
2 3
2 4
2 5

1
0
1
1
0
2
0
2
1
1
5
1
3
1
1

Nguồn

USACO 2019 December Contest, Platinum - Bessie's Snow Cow: https://usaco.org/index.php?page=viewproblem2&cpid=973

Tác giả: Michael Cao và Benjamin Qi.