제3회 디미고 프로그래밍 챌린지 오픈 콘테스트

가중치가 있는 정점 N개로 이루어진 트리가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있다.

트리에서 두 정점 사이의 거리는 두 정점을 연결하는 경로에서 지나야 하는 간선의 수이다.

이 트리에서 다음 두 종류의 쿼리를 총 Q번 수행하려 한다.

쿼리는 다음 두 가지 형식 중 하나로 주어진다:

입력

첫 번째 줄에 정수 N이 주어진다. (2≤N≤3⋅10^5)

두 번째 줄에는 각 정점의 초기 가중치를 나타내는 정수 w_1,\ w_2,\ …,\ w_N이 공백으로 구분하여 주어진다. (−10^9≤w_i≤10^9)

세 번째 줄부터 N−1개의 줄에 걸쳐, 트리를 구성하는 간선의 정보가 주어진다. 각 줄에 두 정수 u,\ v가 주어지며, 이는 정점 u와 v가 간선으로 연결되어 있음을 의미한다. (1≤u,\ v≤N)

다음 줄에 정수 Q가 주어진다. (1≤Q≤3⋅10^5)

이어서 Q개의 줄에 걸쳐 쿼리가 주어진다. 각 쿼리는 다음 형식 중 하나이다:

1 i v (1≤i≤N, −10^9≤v≤10^9)

2 i (1≤i≤N)

2 i 형식의 쿼리는 적어도 한 번 이상 주어진다.

출력

2 i 쿼리가 주어질 때마다, 해당 정점의 현재 가중치를 한 줄에 하나씩 출력한다.

트리와 띄엄띄엄쿼리 3초 1024MB