Truy Vấn Đường Đi Trên Cây

Buổi 42 — LCA & Binary Lifting Buổi 45 — Heavy-Light Decomposition Buổi 52 — Mock Contest Phase 2
Points
45
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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
Draft saved