Heavy-Light Decomposition

Heavy-Light Decomposition

N개의 정점으로 이루어진 루트 있는 트리가 주어진다. 1번 정점이 루트이며, 각 정점에는 초기값이 설정되어 있다. 다음 Q개의 쿼리를 처리하라.

• 1 v w: 정점 v의 값을 w로 변경한다.
• 2 u v: 정점 u에서 정점 v로 가는 경로에 포함된 모든 정점의 값의 합을 출력한다.

입력

첫째 줄에 정점의 개수 N과 쿼리의 개수 Q가 공백으로 구분되어 주어진다.
둘째 줄에 1번 정점부터 N번 정점까지 각 정점의 초기 값이 공백으로 구분되어 주어진다.
셋째 줄부터 N-1개의 줄에 걸쳐 트리를 구성하는 간선의 양끝 정점 u, v가 공백으로 구분되어 주어진다.
다음 줄부터 Q개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.

• 1 ≤ N, Q ≤ 100,000
• 1 ≤ 정점의 초기값, w ≤ 10^6
• 1 ≤ u, v ≤ N (u ≠ v)
• 주어지는 간선들은 트리를 구성한다.

출력

타입 2 쿼리에 대한 결과를 한 줄에 하나씩 출력하라.

예제 입력 1

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

예제 출력 1

7
13

예제 입력 2

3 2
1 1 1
1 2
1 3
2 2 3
2 1 3

예제 출력 2

3
2