write a go solution for 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_1arrowv_1 with x_c, and the count of nodes with value c on path u_2arrowv_2 with y_c. If there are z such values of c such that x_cneqy_c, output any min(z,k) such values in any order.

Input Format:
The first line contains one integer n (1<=n<=10^5) — the number of nodes in the tree.

The next line contains n integers, a_1,a_2,ldots,a_n (1<=a_i<=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<=qu,v<=qn,uneqv) denoting an edge of the tree. It is guaranteed that the given edges form a tree.

The next line contains one integer q (1<=q<=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<=u_1,v_1,u_2,v_2<=n, 1<=qk<=q10).

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.

Note:
For query 1, the first path is 1arrow2arrow4, coming across the multiset of values 5,2,4. On the second path 4arrow2arrow5, 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 4arrow2arrow1arrow3 gives 4,2,5,3. The numbers 5, 2 and 4 occur a different number of times.. Output only the code with no comments, explanation, or additional text.