Снова XOR, снова запросы, снова дерево — романтика (с) Ануар Сериков
Где XOR нет места словам. Итак, давайте двигаться дальше к задаче.
Для корневого дерева с вершинами все вершины пронумерованы от до . На каждой вершине дерева написано одно число — значение вершины. Корнем дерева является вершина .
В этой задаче Вам следует обработать запросов. Запросы бывают двух типов:
— замените все числа, записанные в вершинах поддерева вершины . То есть если в какой-то вершине записано число , то следует заменить его на .
— выведите минимум чисел, записанных на вершинах простого пути из вершины в вершину . Или более формально: пусть числа на пути из вершины в вершину будут , тогда ответом на этот запрос будет минимум этой последовательности.
Первая строка содержит два целых числа — количество вершин в дереве, и — количество запросов.
Вторая строка содержит последовательность из целых чисел — числа, написанные на вершинах.
Затем следуют строка, описывающие ребра дерева. Каждая строка содержит пару целых чисел — вершины, соединенные ребром. Гарантируется, что граф является связным деревом.
Последние строк описывают запросы. Первое число в -й строке — тип -го запроса. Если , то следуют два целых числа и , , иначе следует два целых числа и . Все входные числа являются целыми.
Для каждого запроса 2-го типа выведите в отдельной строке одно целое число — ответ на запрос.
— исключающее OR, например .