Bình luận

• 
  

  0

  N7hoatt    5:01 p.m. 29 Tháng 8, 2023

  Cho một cây gồm \(n\) đỉnh. Các đỉnh được đánh số từ \(1,2,3\dots,n\) và đỉnh \(1\) là gốc của cây. Mỗi đỉnh có một giá trị.

  Hãy thực hiện \(q\) truy vấn có dạng:

  1. Thay đổi giá trị đỉnh \(s\) thành \(x\).
  2. Tìm giá trị lớn nhất trên đường đi từ đỉnh \(a\) tới đỉnh \(b\).

  Input

  • Dòng đầu tiên gồm hai số nguyên \(n\), \(q\): số lượng đỉnh và số lượng truy vấn. Các đỉnh được đánh số từ \(1,2,3,\dots,n\).
  • Dòng tiếp theo gồm \(n\) số nguyên \(v_1,v_2,v_3,\dots,v_n\): giá trị của từng đỉnh.
  • \(n-1\) dòng sau đó biểu diễn các cạnh. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): có cạnh nối giữa \(a\) và \(b\).
  • \(q\) dòng cuối cùng biểu diễn các truy vấn. Mỗi truy vấn có dạng "1 s x" hoặc "2 a b"

  Output

  • In ra kết quả cho truy vấn loại 2.

  Constraints

  • \(1\leq n,q\leq 2 \times 10^5\).
  • \(1\leq a,b,s\leq n\).
  • \(1\leq v_i, x\leq 10^9\).

  Example

  Test

  Input

  5 3
  2 4 1 3 3
  1 2
  1 3
  2 4
  2 5
  2 3 5
  1 2 2
  2 3 5

  Output

  4 3

  Note