CF1957F2.Frequency Mismatch (Hard Version)

这是该问题的困难版本。两种版本的区别在于 $k$ 的约束条件。只有在解决了所有版本的问题后，你才能进行 Hack。

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

你将得到 $q$ 个查询。每个查询给出 $5$ 个整数 $u_1, v_1, u_2, v_2, k$。设 $x_c$ 表示值为 $c$ 的节点在路径 $u_1 \rightarrow v_1$ 上出现的次数，$y_c$ 表示值为 $c$ 的节点在路径 $u_2 \rightarrow v_2$ 上出现的次数。如果存在 $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$，$1 \leq k \leq 10$）。

对于每个查询，输出一行。对于每个查询，先输出 $\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$ 个查询，路径与第 $1$ 个查询相同，但只需输出 $1$ 个值，因此输出 $5$。

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

由 ChatGPT 4.1 翻译