34333번 - @Override

문제

1ドル$번 정점을 루트로 하는 트리가 있다. 트리는 총 $N$개의 정점으로 구성된다.

각 정점 $i$는 정수로 이루어진 가중치 $A_i$를 가지고 있으며, 기본적으로 자신의 가중치인 $A_i$를 사용한다.

아래 두 가지 종류의 쿼리를 처리하는 프로그램을 작성하시오.

• 1ドル$ $i$: 정점 $i$를 루트로 하는 서브 트리의 모든 정점 $v$에 대하여, $i$의 조상의 가중치 중 최댓값을 각 $A_v$에 덮어쓴다. 정점 $i$는 $i$의 조상이 아니다.$(2 \le i \le N)$
• 2ドル$ $i$: 정점 $i$를 루트로 하는 서브 트리의 모든 정점의 가중치의 합을 출력한다. $(1 \le i \le N)$

입력

첫째 줄에 정점의 개수 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. $(2 \le N \le 500,000円;\ 1 \le Q \le 500,000円)$

둘째 줄에 각 정점의 가중치 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$

다음 $N - 1$개의 줄에 트리의 간선을 나타내는 두 정점 $u,\ v$가 공백으로 구분되어 주어진다. $(1 \le u,\ v \le N;\ u \ne v)$

이어서 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.

2ドル$번 쿼리가 하나 이상 주어짐이 보장된다.

입력되는 모든 수는 정수이다.

출력

모든 2ドル$번 쿼리의 결과를 입력된 순서대로 각 줄에 하나씩 출력한다.

제한

힌트