311261: CF1957F1. Frequency Mismatch (Easy Version)
Description
This is the easy version of the problem. The difference between the two versions of this problem is the constraint on $k$. You can make hacks only if all versions of the problem are solved.
You are given an undirected tree of $n$ nodes. Each node $v$ has a value $a_v$ written on it. You have to answer queries related to the tree.
You are given $q$ queries. In each query, you are given $5$ integers, $u_1, v_1, u_2, v_2, k$. Denote the count of nodes with value $c$ on path $u_1 \rightarrow v_1$ with $x_c$, and the count of nodes with value $c$ on path $u_2 \rightarrow v_2$ with $y_c$. If there are $z$ such values of $c$ such that $x_c \neq y_c$, output any $\min(z, k)$ such values in any order.
InputThe first line contains one integer $n$ ($1 \leq n \leq 10^5$) — the number of nodes in the tree.
The next line contains $n$ integers, $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^5$) — the value written on each node of the tree.
Then $n - 1$ lines follow. Each line contains two integers $u$ and $v$ ($1 \leq u, v \leq n, u \neq v$) denoting an edge of the tree. It is guaranteed that the given edges form a tree.
The next line contains one integer $q$ ($1 \leq q \leq 10^5$) — the number of queries.
Then $q$ lines follow. Each line contains five integers $u_1, v_1, u_2, v_2, k$ ($1 \leq u_1, v_1, u_2, v_2 \leq n$, $k = 1$).
OutputFor each query, output on a separate line. For a query, first output $\min(z, k)$ and then on the same line, output any $\min(z, k)$ values in any order which occur a different number of times in each path.
ExampleInput5 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 1Output
1 5 0 1 2Note
For query $1$, the first path is $1 \rightarrow 2 \rightarrow 4$, coming across the multiset of values $\{5, 2, 4\}$. On the second path $4 \rightarrow 2 \rightarrow 5$, we have the multiset $\{4, 2, 3\}$. Two numbers — $3$ and $5$ occur a different number of times, hence we print one of them.
In query $2$, there is no difference between the paths, hence we output $0$.
In query $3$, the first path is just the node $5$, resulting in the multiset $\{3\}$, and the second path $4 \rightarrow 2 \rightarrow 1 \rightarrow 3$ gives $\{4, 2, 5, 3\}$. The numbers $5$, $2$ and $4$ occur a different number of times.
Output
这是一个关于树的问题的简单版本。在这个问题中，你会得到一个有n个节点的无向树，每个节点v上都有一个值a_v。你需要回答与树相关的查询。你有q个查询，每个查询包含5个整数，u1, v1, u2, v2, k。用x_c表示路径u1→v1上值为c的节点的数量，用y_c表示路径u2→v2上值为c的节点的数量。如果有z个这样的c值使得x_c ≠ y_c，那么按任意顺序输出z和k中的最小值个这样的c值。
输入数据格式：
第一行包含一个整数n（1≤n≤10^5）——树中的节点数。
接下来一行包含n个整数，a1, a2, …, an（1≤a_i≤10^5）——树上每个节点的值。
然后是n-1行，每行包含两个整数u和v（1≤u, v≤n, u≠v），表示树的一条边。保证给定的边构成一棵树。
接下来一行包含一个整数q（1≤q≤10^5）——查询的数量。
然后是q行，每行包含五个整数u1, v1, u2, v2, k（1≤u1, v1, u2, v2≤n，k=1）。
输出数据格式：
对于每个查询，输出一行。首先输出z和k中的最小值，然后在同一行中按任意顺序输出z和k中的最小值个这样的c值，这些值在每条路径中出现的次数不同。
示例：
输入：
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 5
0
1 2
注意：
在第一个查询中，第一条路径是1→2→4，遇到值集合{5, 2, 4}。在第二条路径4→2→5上，我们有值集合{4, 2, 3}。两个数字——3和5出现的次数不同，因此我们打印其中一个。
在第二个查询中，两条路径之间没有差异，因此我们输出0。
在第三个查询中，第一条路径只是节点5，得到值集合{3}，第二条路径4→2→1→3给出值集合{4, 2, 5, 3}。数字5、2和4出现的次数不同。题目大意： 这是一个关于树的问题的简单版本。在这个问题中，你会得到一个有n个节点的无向树，每个节点v上都有一个值a_v。你需要回答与树相关的查询。你有q个查询，每个查询包含5个整数，u1, v1, u2, v2, k。用x_c表示路径u1→v1上值为c的节点的数量，用y_c表示路径u2→v2上值为c的节点的数量。如果有z个这样的c值使得x_c ≠ y_c，那么按任意顺序输出z和k中的最小值个这样的c值。 输入数据格式： 第一行包含一个整数n（1≤n≤10^5）——树中的节点数。 接下来一行包含n个整数，a1, a2, …, an（1≤a_i≤10^5）——树上每个节点的值。 然后是n-1行，每行包含两个整数u和v（1≤u, v≤n, u≠v），表示树的一条边。保证给定的边构成一棵树。 接下来一行包含一个整数q（1≤q≤10^5）——查询的数量。 然后是q行，每行包含五个整数u1, v1, u2, v2, k（1≤u1, v1, u2, v2≤n，k=1）。 输出数据格式： 对于每个查询，输出一行。首先输出z和k中的最小值，然后在同一行中按任意顺序输出z和k中的最小值个这样的c值，这些值在每条路径中出现的次数不同。 示例： 输入： 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 5 0 1 2 注意： 在第一个查询中，第一条路径是1→2→4，遇到值集合{5, 2, 4}。在第二条路径4→2→5上，我们有值集合{4, 2, 3}。两个数字——3和5出现的次数不同，因此我们打印其中一个。 在第二个查询中，两条路径之间没有差异，因此我们输出0。 在第三个查询中，第一条路径只是节点5，得到值集合{3}，第二条路径4→2→1→3给出值集合{4, 2, 5, 3}。数字5、2和4出现的次数不同。