28402번 - 두 트리

문제

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

제한

힌트