Two Trees

Two trees $T_1$, $T_2$ and a sequence $a_1, a_2, \cdots, a_N$ are given. Each tree has $N$ vertices, and the vertices are numbered from 1 to $N$ with no repeats. The root of both trees is vertex 1.

In $T_1$ and $T_2$, let $P_i$ and $Q_i$ be the sets of vertex numbers in the subtree rooted at vertex $i$, respectively. Define $m_i = \max\{a_k \mid k \in P_i \cap Q_i\}$.

Write a program that computes $m_1, m_2, \cdots, m_N$.

The first line contains $N$. $(1 \leq N \leq 250\,000)$

The second line contains the integers $a_1, a_2, \cdots, a_N$, separated by spaces. $(1 \leq a_i \leq 10^9)$

The next $N-1$ lines each contain two integers $u$ and $v$, separated by a space, that are the endpoints of an edge of $T_1$. $(1 \leq u, v \leq N;\ u \neq v)$

The next $N-1$ lines each contain two integers $u$ and $v$, separated by a space, that are the endpoints of an edge of $T_2$. $(1 \leq u, v \leq N;\ u \neq v)$

It is guaranteed that $T_1$ and $T_2$ are trees.

Print $m_1, m_2, \cdots, m_N$, one per line, in order.