SOJ ONLINE JUDGE

트리 경로 최댓값

난이도: Platinum I 출제자: rlatjwls7882 시간 제한: 1000 ms 메모리 제한: 512 MB
세그먼트 트리Heavy-light 분할

$1$번부터 $N$번까지 번호가 붙은 정점으로 이루어진 트리가 있다. 각 정점 $i$에는 정수 $A_i$가 적혀 있다.

$Q$개의 쿼리를 순서대로 처리하라. 쿼리는 다음 중 하나이다.

  • 1 u x: $A_u$를 $x$로 바꾼다. $(1 \leq u \leq N,\ -10^9 \leq x \leq 10^9)$
  • 2 u v: $u$번 정점에서 $v$번 정점으로 가는 단순 경로에 포함된 정점에 적힌 값의 최댓값을 출력한다. $(1 \leq u,v \leq N)$

입력

첫 번째 줄에 정점의 개수 $N$과 쿼리의 개수 $Q$가 주어진다. $(1 \leq N,Q \leq 200\,000)$

두 번째 줄에 각 정점에 적힌 값 $A_1,A_2,\ldots,A_N$이 주어진다. $(-10^9 \leq A_i \leq 10^9)$

세 번째 줄부터 $N-1$개의 줄에 걸쳐 간선으로 연결된 두 정점 $u$, $v$가 주어진다. $(1 \leq u,v \leq N,\ u \neq v)$

그 다음 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.

출력

2 u v 쿼리마다 경로 최댓값을 한 줄에 하나씩 출력한다.

예제 입력 1

5 7
3 -2 5 1 4
1 2
1 3
2 4
2 5
2 4 3
1 2 10
2 4 3
2 5 4
1 3 -5
2 3 5
2 1 1

예제 출력 1

5
10
10
10
3

제출