Truy Vấn Đường Đi Trên Cây
Points
45
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho cây gồm N đỉnh, mỗi đỉnh i có giá trị a_i. Cây có gốc tại đỉnh 1.
Cho Q truy vấn, mỗi truy vấn thuộc một trong hai loại:
- Loại 1 u x: Gán giá trị đỉnh u thành x.
- Loại 2 u v: Tìm giá trị lớn nhất 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 (1 ≤ N, Q ≤ 100000).
Dòng thứ hai chứa N số nguyên a_1, a_2, ..., a_N (1 ≤ a_i ≤ 10^9).
N-1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u v (1 ≤ u, v ≤ N) mô tả một cạnh.
Q dòng tiếp theo, mỗi dòng chứa truy vấn theo định dạng trê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.
Ví dụ
| Input | Output |
|---|---|
| 5 4\n1 3 5 2 4\n1 2\n1 3\n2 4\n3 5\n2 4 5\n1 3 10\n2 4 5\n2 1 4 | 5\n10\n3 |
Giới hạn
- 1 ≤ N, Q ≤ 100000
- 1 ≤ a_i, x ≤ 10^9
Community Discussion