← 返回题目列表

Codeforces · 1957/F2

F2. 频率不匹配(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。该问题的两个版本之间的区别在于 $$$k$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

给你一个由 $$$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)$$$ 这样的值。

输入

第一行包含一个整数 $$$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

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$$$,第一个路径是 $$$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$$$ 出现的次数不同。