Frequency Mismatch (Hard Version)
Contest: Codeforces Round 940 (Div. 2) and CodeCraft-23
Difficulty rating: 2700
Tags: binary search, data structures, dfs and similar, hashing, probabilities, trees

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.

Input format:
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 format:
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.

Constraints:
Time limit: 4.5 s
Memory limit: 512.0 MB

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.

Example 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

Example output:
2 3 5
0
1 5
3 5 2 4

Editorial:
Let's start by first solving the problem for $$$k = 1$$$, and extend the idea to $$$k > 1$$$ later. To solve for $$$k = 1$$$, we'll find the smallest value that occurs with different frequencies on the two paths.
We'll solve an easier version by solving for two static arrays, instead of solving the problem of two paths. To find the smallest value that has a different frequency between the two arrays, we can have a segment tree on the frequency array for each static array. Then, we can store the hash of each segment tree node and perform a descent to find the first point at which the hashes in the two segment trees differ. The hash of a node is the polynomial hash of the subarray it corresponds to.
Now, in order to use the same technique on the path, we want the frequency array of the path $$$u \rightarrow v$$$. To achieve this, we can use persistent segment trees. We define $$$seg(u \rightarrow v)$$$ to be the segment tree that corresponds to the frequency array of the values on the path $$$u \rightarrow v$$$. With the idea of persistence, we can quickly compute $$$seg(1 \rightarrow u)$$$ for all $$$u$$$, when we root at $$$1$$$.
To compute $$$seg(u \rightarrow v)$$$, we can use this:
$$$seg(u \rightarrow v) = seg(1 \rightarrow u) + seg(1 \rightarrow v) - seg(1 \rightarrow lca(u, v)) - seg(1 \rightarrow parent(lca(u, v)))$$$ for every node in the segment tree that we want.
Hence, we are able to get the segment tree for the two paths we need to compare in a query. In our solution with the static arrays, we used the polynomial hash to find the first point of difference between the two frequency arrays. So, we need a way to quickly compute the hash of the pseudo node we computed for $$$seg(u \rightarrow v)$$$.
If we have two frequency arrays $$$f_1$$$, $$$f_2$$$, $$$hash(f_1) + hash(f_2) = hash(f_1 + f_2)$$$, where the hash of a node is the polynomial hash of the subarray that corresponds to that node.
Hence, we can say:
$$$hash(seg(u \rightarrow v)) = hash(seg(1 \rightarrow u)) + hash(seg(1 \rightarrow v)) - hash(seg(1 \rightarrow lca(u, v))) - hash(seg(1 \rightarrow parent(lca(u, v)))$$$
Hence, we can perform the same descent that we talked about earlier on the derived segment tree.
Now to solve this for $$$k > 1$$$, you can perform a dfs on $$$seg(u \rightarrow v)$$$, and keep entering nodes of the segment tree which have differing hashes, until we find $$$k$$$ values.
The total time complexity comes out to $$$O(nlogn) + O(q) \times O(k) \times O(logn) = O(qklogn + nlogn)$$$