Đỉnh cao nhất hành trình
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề 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$.
Community Discussion