Primitive Queries

Điểm: 0,70 (OI)

Giới hạn thời gian: 5.0s

Giới hạn bộ nhớ: 1G

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một cây gồm ~n~ đỉnh và ~Q~ truy vấn. Trên mỗi đỉnh ~u~ của cây được gán một giá trị là ~C_u~. Mỗi truy vấn sẽ thuộc ~1~ trong ~2~ dạng như sau:

~1~ ~u~ ~v~ ~(1 \le u,v \le n)~ : tìm số các số khác nhau trong đường đi từ ~u~ đến ~v~.
~2~ ~x~ ~val~ ~(1 \le x \le n;~ ~0 \le val \le 10^9)~: gán giá trị ~val~ vào ~C_x~.

Dòng đầu tiên bao gồm hai số ~n~ và ~Q~ lần lượt là số đỉnh của cây và số truy vấn của bài (~1 \le n, Q \le 10^5~).
Dòng thứ hai chứa ~n~ số nguyên là các giá trị ~C_1, C_2, \dots, C_n~ (~0 \le C_i \le 10^9~).
~n - 1~ dòng tiếp theo chứa các cạnh của cây và trong đó mỗi dòng sẽ chứa ~2~ số ~u~ và ~v~ là hai đỉnh được nối với nhau bởi ~1~ cạnh (~1 \le u, v \le n~).
~Q~ dòng tiếp theo lần lượt là các truy vấn của bài toán.

Ở mỗi truy vấn loại ~1~ sẽ in ra đáp án của truy vấn trên một dòng duy nhất.

Subtask	Điểm	Giới hạn
1	~50~	Chỉ bao gồm các truy vấn loại ~1~
2	~50~	không có giới hạn gì thêm

6 7
1 2 3 4 5 6
1 2
1 3
2 4
2 5
3 6
1 5 6
2 5 6
1 1 5
1 5 6
2 1 6
1 5 6
1 2 6

Bình luận

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