CF1767F Two Subtrees

给定一棵有 $n$ 个结点的有根树，根为结点 $1$。每个结点上写有一个整数，第 $i$ 个结点上的整数为 $val_i$。 你需要处理 $q$ 个关于这棵树的询问。第 $i$ 个询问由两个结点 $u_i$ 和 $v_i$ 表示。对于每个询问，考虑所有在 $u_i$ 的子树或 $v_i$ 的子树中的结点（如果某个结点同时在两个子树中，则计数两次）。将这两个子树中所有结点上的整数列出来，找出出现次数最多的整数。如果有多个整数出现次数相同，则输出其中最小的一个。

第一行包含一个整数 $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$），表示树中的一条边。 接下来一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示询问的数量。 接下来 $q$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$），表示第 $i$ 个询问的两个子树的根。

对于每个询问，输出一个整数，表示在对应的两个子树中出现次数最多的数字（如果有多个，输出最小的那个）。

在第 $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$。 由 ChatGPT 4.1 翻译