这是问题的简单版本。该问题的两个版本之间的区别在于 $$$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$$$, $$$k = 1$$$)。
输出
对于每个查询,在单独的行上输出。对于查询,首先输出 $$$\min(z, k)$$$,然后在同一行上以任意顺序输出在每个路径中出现不同次数的任何 $$$\min(z, k)$$$ 值。
示例
输入 #1
5 5 2 3 4 3 1 2 1 3 2 4 2 5 3 1 4 4 5 1 2 3 2 3 1 5 5 4 3 1
输出 #1
1 5 0 1 2
注意
对于查询 $$$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$$$ 出现的次数不同。