Снова XOR, снова запросы, снова дерево — романтика (с) Ануар Сериков
Где XOR нет места словам. Итак, давайте двигаться дальше к задаче.
Для корневого дерева с n вершинами все вершины пронумерованы от 1 до n. На каждой вершине дерева написано одно число — значение вершины. Корнем дерева является вершина 1.
В этой задаче Вам следует обработать q запросов. Запросы бывают двух типов:
1 v x — замените все числа, записанные в вершинах поддерева вершины v. То есть если в какой-то вершине записано число y, то следует заменить его на x⊕y.
2 u v — выведите минимум чисел, записанных на вершинах простого пути из вершины u в вершину v. Или более формально: пусть числа на пути из вершины u в вершину v будут a1,a2,...,ak, тогда ответом на этот запрос будет минимум этой последовательности.
Первая строка содержит два целых числа n (1≤n≤3∗104) — количество вершин в дереве, и q (1≤q≤3∗104) — количество запросов.
Вторая строка содержит последовательность из n целых чисел a1,a2,…,an (0≤ai<220) — числа, написанные на вершинах.
Затем следуют n−1 строка, описывающие ребра дерева. Каждая строка содержит пару целых чисел xi,yi (1≤xi,yi≤n,xi=yi) — вершины, соединенные ребром. Гарантируется, что граф является связным деревом.
Последние q строк описывают запросы. Первое число в i-й строке typei — тип i-го запроса. Если typei=1, то следуют два целых числа vi и xi (1≤vi≤n, 0≤xi<220), иначе следует два целых числа ui и vi (1≤ui,vi≤n). Все входные числа являются целыми.
Для каждого запроса 2-го типа выведите в отдельной строке одно целое число — ответ на запрос.
⊕ — исключающее OR, например 3⊕5=6.