311262: CF1957F2. Frequency Mismatch (Hard Version)
Description
This is the hard 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$, $1 \leq k \leq 10$).
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 4 1 4 4 5 3 2 3 2 3 1 1 4 4 5 1 5 5 4 3 10Output
2 3 5 0 1 5 3 5 2 4Note
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 them both.
In query $2$, there is no difference between the paths, hence we output $0$.
In query $3$, we have the same paths as query $1$, but we need to output only $1$ value, hence we output $5$.
In query $4$, 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(1≤n≤10^5),表示树中的节点数。
- 第二行包含n个整数a_1, a_2, ..., a_n(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,1≤k≤10)。
输出数据格式:
- 对于每个查询,输出一行。首先输出min(z, k),然后在同一行输出任意min(z, k)个出现次数不同的数值,可以按任意顺序输出。
示例:
Input
```
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
```
Output
```
2 3 5
0
1 5
3 5 2 4
```题目大意:给定一个包含n个节点的无向树,每个节点上都有一个值a_v。需要回答关于树的查询。查询包含q个,每个查询包含5个整数,u1, v1, u2, v2, k。对于每个查询,找出两条路径u1→v1和u2→v2上,出现次数不同的数值,输出其中任意min(z, k)个值,其中z是出现次数不同的数值的个数。 输入数据格式: - 第一行包含一个整数n(1≤n≤10^5),表示树中的节点数。 - 第二行包含n个整数a_1, a_2, ..., a_n(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,1≤k≤10)。 输出数据格式: - 对于每个查询,输出一行。首先输出min(z, k),然后在同一行输出任意min(z, k)个出现次数不同的数值,可以按任意顺序输出。 示例: Input ``` 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 ``` Output ``` 2 3 5 0 1 5 3 5 2 4 ```