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.
55 2 3 4 31 21 32 42 541 4 4 5 32 3 2 3 11 4 4 5 15 5 4 3 10
2 3 5 0 1 5 3 5 2 4
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.
Name |
---|