Это простая версия задачи. Единственное отличие между версиями — ограничение на $$$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$$$, $$$k = 1$$$).
Для каждого запроса выведите ответ на отдельной строке. Для каждого запроса сначала выведите $$$\min(z, k)$$$, а затем в той же строке выведите любые $$$\min(z, k)$$$ значений, которые встречаются разное количество раз на путях, в любом порядке.
5 5 2 3 4 3 1 2 1 3 2 4 2 5 3 1 4 4 5 1 2 3 2 3 1 5 5 4 3 1
1 5 0 1 2
Для $$$1$$$ запроса первый путь: $$$1 \rightarrow 2 \rightarrow 4$$$, на котором встречается мультинабор значений $$$\{5, 2, 4\}$$$. На втором пути $$$4 \rightarrow 2 \rightarrow 5$$$ мы имеем мультинабор $$$\{4, 2, 3\}$$$. Два числа — $$$3$$$ и $$$5$$$ встречаются разное количество раз, поэтому мы выводим одно из них.
Во $$$2$$$ запросе пути совпадают, поэтому выводим $$$0$$$.
В $$$3$$$ запросе первый путь — только вершина $$$5$$$, что приводит к мультинабору $$$\{3\}$$$, а второй путь — $$$4 \rightarrow 2 \rightarrow 1 \rightarrow 3$$$ дает $$$\{4, 2, 5, 3\}$$$. Числа $$$5$$$, $$$2$$$ и $$$4$$$ встречаются разное количество раз.
