Это сложная версия задачи. Единственное отличие между версиями — ограничение на $$$k$$$. Вы можете делать взломы, только если обе версии задачи решены.
Вам дано неориентированное дерево из $$$n$$$ вершин. На каждой вершине $$$v$$$ записано значение $$$a_v$$$. Вы должны ответить на запросы, связанные с деревом.
Вам дано $$$q$$$ запросов. В каждом запросе дается $$$5$$$ целых чисел, $$$u_1, v_1, u_2, v_2, k$$$. Обозначим количество вершин со значением $$$c$$$ на пути $$$u_1 \rightarrow v_1$$$ как $$$x_c$$$, а количество вершин со значением $$$c$$$ на пути $$$u_2 \rightarrow v_2$$$ как $$$y_c$$$. Пусть существует $$$z$$$ таких значений $$$c$$$, что $$$x_c \neq y_c$$$. Тогда выведите любые $$$\min(z, k)$$$ таких значений в любом порядке.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество вершин в дереве.
Следующая строка содержит $$$n$$$ целых чисел, $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — значения, записанные на каждой вершине дерева.
Затем следует $$$n - 1$$$ строка. Каждая строка содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n, u \neq v$$$), обозначающие ребро дерева. Гарантируется, что заданные ребра образуют дерево.
Следующая строка содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — количество запросов.
Затем следуют $$$q$$$ строк. Каждая строка содержит пять целых чисел $$$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$$$).
Для каждого запроса выведите ответ на отдельной строке. Для каждого запроса сначала выведите $$$\min(z, k)$$$, а затем в той же строке выведите любые $$$\min(z, k)$$$ значений, которые встречаются разное количество раз на путях, в любом порядке.
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
Для $$$1$$$ запроса первый путь: $$$1 \rightarrow 2 \rightarrow 4$$$, на котором встречается мультинабор значений $$$\{5, 2, 4\}$$$. На втором пути $$$4 \rightarrow 2 \rightarrow 5$$$ мы имеем мультинабор $$$\{4, 2, 3\}$$$. Два числа — $$$3$$$ и $$$5$$$ встречаются разное количество раз, поэтому мы выводим оба числа.
Во $$$2$$$ запросе пути совпадают, поэтому выводим $$$0$$$.
В $$$3$$$ запросе у нас те же пути, что и в запросе $$$1$$$, но нам нужно вывести только $$$1$$$ значение, поэтому мы выводим $$$5$$$.
В $$$4$$$ запросе первый путь — только вершина $$$5$$$, что приводит к мультинабору $$$\{3\}$$$, а второй путь — $$$4 \rightarrow 2 \rightarrow 1 \rightarrow 3$$$ дает $$$\{4, 2, 5, 3\}$$$. Числа $$$5$$$, $$$2$$$ и $$$4$$$ встречаются разное количество раз.
