두 트리

두 트리 $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}$을 차례로 한 줄에 하나씩 출력한다.