CF1957F1.Frequency Mismatch (Easy Version)

这是该问题的简单版本。两种版本的区别在于 $k$ 的限制。只有在解决了所有版本的问题后，你才能进行 hack。

给定一棵有 $n$ 个节点的无向树。每个节点 $v$ 上写有一个值 $a_v$。你需要回答与这棵树相关的若干查询。

你将得到 $q$ 个查询。每个查询给出 $5$ 个整数 $u_1, v_1, u_2, v_2, k$。设 $x_c$ 表示在路径 $u_1 \rightarrow v_1$ 上值为 $c$ 的节点个数，$y_c$ 表示在路径 $u_2 \rightarrow v_2$ 上值为 $c$ 的节点个数。如果存在 $z$ 个不同的 $c$ 使得 $x_c \neq y_c$，请输出任意 $\min(z, k)$ 个这样的 $c$，顺序不限。

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示树的节点数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^5$），表示每个节点上的值。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n, u \neq v$），表示树中的一条边。保证这些边构成一棵树。

接下来一行包含一个整数 $q$（$1 \leq q \leq 10^5$），表示查询的数量。

接下来 $q$ 行，每行包含五个整数 $u_1, v_1, u_2, v_2, k$（$1 \leq u_1, v_1, u_2, v_2 \leq n$，$k=1$）。

对于每个查询，输出一行。对于每个查询，先输出 $\min(z, k)$，然后在同一行输出任意 $\min(z, k)$ 个在两条路径上出现次数不同的值，顺序不限。

对于第 1 个查询，第一条路径为 $1 \rightarrow 2 \rightarrow 4$，路径上的值为 $\{5, 2, 4\}$。第二条路径 $4 \rightarrow 2 \rightarrow 5$，路径上的值为 $\{4, 2, 3\}$。有两个数字 $3$ 和 $5$ 出现次数不同，因此输出其中一个即可。

对于第 2 个查询，两条路径完全相同，因此输出 $0$。

对于第 3 个查询，第一条路径仅为节点 $5$，值为 $\{3\}$，第二条路径 $4 \rightarrow 2 \rightarrow 1 \rightarrow 3$，值为 $\{4, 2, 5, 3\}$。数字 $5$、$2$ 和 $4$ 出现次数不同。

由 ChatGPT 4.1 翻译