두 트리

두 트리 $T_1$, $T_2$와 수열 $a_1, a_2, \cdots, a_N$이 주어진다. 두 트리는 각각 정점을 $N$개 가지며, 정점에는 1부터 $N$까지의 번호가 겹치지 않게 붙어 있다. 두 트리의 루트는 모두 1번 정점이다.

$T_1$과 $T_2$에서 $i$번 정점을 루트로 하는 서브트리에 속한 정점 번호의 집합을 각각 $P_i$, $Q_i$라 하자. $m_i = \max\{a_k \mid k \in P_i \cap Q_i\}$로 정의한다.

$m_1, m_2, \cdots, m_N$을 구하는 프로그램을 작성하시오.

첫 번째 줄에 $N$이 주어진다. $(1 \leq N \leq 250\,000)$

두 번째 줄에 정수 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어진다. $(1 \leq a_i \leq 10^9)$

다음 $N-1$개의 줄에는 $T_1$의 각 간선이 잇는 두 정점의 번호 $u$, $v$가 공백으로 구분되어 주어진다. $(1 \leq u, v \leq N;\ u \neq v)$

그다음 $N-1$개의 줄에는 $T_2$의 각 간선이 잇는 두 정점의 번호 $u$, $v$가 공백으로 구분되어 주어진다. $(1 \leq u, v \leq N;\ u \neq v)$

$T_1$과 $T_2$가 트리 형태임이 보장된다.

$m_1, m_2, \cdots, m_N$을 차례로 한 줄에 하나씩 출력한다.