Frequency Mismatch（困难版）

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

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

每次询问给出 $u_1,v_1,u_2,v_2,k$。设 $x_c$ 为值 $c$ 在路径 $u_1\to v_1$ 上的出现次数，$y_c$ 为值 $c$ 在路径 $u_2\to v_2$ 上的出现次数。如果共有 $z$ 个不同的值 $c$ 满足 $x_c\ne y_c$，请输出任意 $\min(z,k)$ 个这样的值，顺序不限。

这是困难版本，其中 $k$ 的上限为 $10$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示树中的一条边。

接下来一行一个整数 $q$，表示询问数。

接下来 $q$ 行，每行五个整数 $u_1,v_1,u_2,v_2,k$。

输出格式

对每次询问输出一行。先输出 $\min(z,k)$，再输出任意这么多个在两条路径中出现次数不同的值。所选值必须互不相同，顺序不限。

样例输入 1

5
5 2 3 4 3
1 2
1 3
2 4
2 5
4
1 4 4 5 3
2 3 2 3 1
1 4 4 5 1
5 5 4 3 10

样例输出 1

2 3 5
0
1 5
3 5 2 4

数据范围

对于所有数据：

• $1\le n,q\le 10^5$；
• $1\le a_i\le 10^5$；
• $1\le u_1,v_1,u_2,v_2\le n$；
• $1\le k\le 10$；
• 输入边构成一棵树。

每个测试点独立计分。

说明

样例的第一组路径值多重集分别为 $\{5,2,4\}$ 与 $\{4,2,3\}$，因此 $3$ 和 $5$ 的出现次数不同。输出可以选择任意满足要求的值，不必与样例一致。