Đỉnh cao nhất hành trình

Buổi 45 — Heavy-Light Decomposition
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một cây $N$ đỉnh, đỉnh $i$ ban đầu có độ cao $A_i$. Thực hiện $Q$ thao tác:

  • 1 u x: Thay đổi độ cao của đỉnh $u$ thành $x$.
  • 2 u v: Tìm độ cao lớn nhất trong số các đỉnh nằm trên đường đi từ $u$ đến $v$.
Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, Q$.
  • Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.
  • $N - 1$ dòng tiếp theo chứa các cạnh $u, v$ của cây.
  • $Q$ dòng cuối cùng, mỗi dòng là một truy vấn.
Dữ liệu ra

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

Ví dụ
Input Output
5 4
4 1 7 3 9
1 2
1 3
2 4
2 5
2 4 3
1 2 10
2 4 5
2 1 1
7
10
4
Giới hạn

$1 \le N, Q \le 10^5$, $|A_i|, |x| \le 10^9$.

Draft saved