CF1767F.Two Subtrees

You are given a rooted tree consisting of $n$ vertices. The vertex $1$ is the root. Each vertex has an integer written on it; this integer is $val_i$ for the vertex $i$.

You are given $q$ queries to the tree. The $i$-th query is represented by two vertices, $u_i$ and $v_i$. To answer the query, consider all vertices $w$ that lie in the subtree of $u_i$ or $v_i$ (if a vertex is in both subtrees, it is counted twice). For all vertices in these two subtrees, list all integers written on them, and find the integer with the maximum number of occurrences. If there are multiple integers with maximum number of occurrences, the minimum among them is the answer.

给你一棵包含 $n$ 个顶点的有根树，其中顶点 $1$ 为根。每个顶点上写有一个整数；顶点 $i$ 上的整数记为 $val_i$。

你将收到 $q$ 个关于该树的查询。第 $i$ 个查询由两个顶点 $u_i$ 和 $v_i$ 表示。为了回答该查询，请考虑所有位于 $u_i$ 的子树中或 $v_i$ 的子树中的顶点 $w$（若某个顶点同时属于两个子树，则它被计算两次）。对这两个子树中的所有顶点，列出其上所写的全部整数，并找出出现次数最多的那个整数。如果存在多个整数具有相同的最大出现次数，则答案为其中最小的那个整数。

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

The second line contains $n$ integers $val_1, val_2, \dots, val_n$ ($1 \le val_i \le 2 \cdot 10^5$) — the numbers written on the vertices.

Then $n - 1$ lines follow, each containing two integers $x$ and $y$ ($1 \le x, y \le n$) representing an edge between vertices $x$ and $y$. These edges form a tree.

The next line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries to process.

Then $q$ lines follow. The $i$-th of them containing two numbers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) — the roots of subtrees in the $i$-th query.

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——树中顶点的数量。

第二行包含 $n$ 个整数 $val_1, val_2, \dots, val_n$（$1 \le val_i \le 2 \cdot 10^5$）——写在各顶点上的数值。

接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$），表示顶点 $x$ 与 $y$ 之间的一条边。这些边构成一棵树。

接下来一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）——需要处理的查询数量。

随后是 $q$ 行，其中第 $i$ 行包含两个数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$）——第 $i$ 个查询中两棵子树的根节点。

For each query, print one integer — the number that has the maximum amount of occurrences in the corresponding pair of subtrees (if there are multiple such numbers, print the minimum one among them).

对于每个查询，输出一个整数——该整数是在对应的一对子树中出现次数最多的数字（如果存在多个这样的数字，则输出其中最小的一个）。

In the $1$-st query, the pair of subtrees consists of vertices $[2, 4, 7, 8]$, and the numbers written on them are ${1, 2, 2, 4}$. The number $2$ occurs twice, all other numbers — at most once, so the answer is $2$.

In the $2$-nd query, the pair of subtrees consists of vertices $[3, 5, 6, 7, 7, 8, 8]$, and the numbers written on them are ${3, 3, 3, 2, 2, 4, 4}$. The number $3$ has the maximum number of occurrences.

In the $4$-th query, the pair of subtrees consists of vertices $[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8]$, and the numbers written on them are ${2, 2, 1, 1, 3, 3, 2, 2, 3, 3, 3, 3, 2, 2, 4, 4}$. The numbers $2$ and $3$ are the most common, the minimum of them is $2$.

在第 $1$ 次查询中，该子树对包含顶点 $[2, 4, 7, 8]$，其上所写的数字为 $\{1, 2, 2, 4\}$。数字 $2$ 出现了两次，其余所有数字至多出现一次，因此答案为 $2$。

在第 $2$ 次查询中，该子树对包含顶点 $[3, 5, 6, 7, 7, 8, 8]$，其上所写的数字为 $\{3, 3, 3, 2, 2, 4, 4\}$。数字 $3$ 的出现次数最多。

在第 $4$ 次查询中，该子树对包含顶点 $[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8]$，其上所写的数字为 $\{2, 2, 1, 1, 3, 3, 2, 2, 3, 3, 3, 3, 2, 2, 4, 4\}$。数字 $2$ 和 $3$ 出现次数并列最多，其中较小者为 $2$。