Truy vấn đường đi II

Cho một cây gồm $n$ đỉnh, gốc tại đỉnh 1. Mỗi đỉnh có một giá trị ban đầu. Xử lý $q$ thao tác:

• Loại 1: Cập nhật giá trị của một đỉnh.
• Loại 2: 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 hai số nguyên $n$ và $q$.

Dòng thứ hai chứa $n$ số nguyên là giá trị ban đầu của các đỉnh từ $1$ đến $n$.

• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ mô tả một cạnh của cây.

• $q$ dòng tiếp theo, mỗi dòng là một thao tác:

• 1 s x — cập nhật giá trị đỉnh $s$ thành $x$.
• 2 a b — tìm giá trị lớn nhất trên đường đi giữa $a$ và $b$.

Dữ liệu ra

Với mỗi thao tác loại 2, in ra giá trị lớn nhất. Tất cả kết quả in trên một dòng, cách nhau bởi dấu cách.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $1\le v_i,x\le {10}^9$
• $1\le a,b,s\le n$

Ví dụ