codeforces#P1957F2. Frequency Mismatch (Hard Version)
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.
The 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$).
For 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.
Input
The 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$).
Output
For 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.
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
2 3 5
0
1 5
3 5 2 4
Note
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.