CF1957F2 Frequency Mismatch (Hard Version)

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.

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.