Truy vấn đường đi II (Path Queries II)

Nguồn: CSES

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

Đề bài

Cho một cây, mỗi đỉnh có một giá trị. Hỗ trợ đổi giá trị tại một đỉnh và tìm giá trị lớn nhất trên đường đi giữa hai đỉnh.

Dữ liệu vào

Dòng đầu chứa $n,q$, dòng hai chứa giá trị các đỉnh, tiếp theo $n-1$ cạnh. Mỗi truy vấn là 1 s x hoặc 2 a b.

Kết quả

Với mỗi truy vấn loại 2, in giá trị lớn nhất trên đường đi.

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$, $1\le v_i,x\le10^9$.

Ví dụ

Input

1 11
142
1 1 816
2 1 1
1 1 696
1 1 902
2 1 1
1 1 791
1 1 73
2 1 1
1 1 361
1 1 711
2 1 1

Output

816
902
73
711

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.