@Lddrnox

Помогите решить задачу
В Ксении имеется корневое дерево из n вершин с корнем в вершине 1, где на каждой вершине записано число. На i-й вершине записано число a(i).
Напомним, что дерево называется связной граф без циклов. Корневым деревом называется дерево, в котором выбрана одна вершина – корень.
Предком вершины v в корневом дереве называют все вершины, лежащие по пути от v к корню кроме самой вершины v. Поддеревьем вершины v называют множество всех вершин, для которых v является предком и саму вершину v.
XOR суммой множества S=(u1 ,u2 ,u3,…,uk) называется число u1⊕u2⊕u3⊕⋯⊕uk, где ⊕ — операция побитовой исключительной дизъюнкции, обозначаемая как «xor» в языке Pascal и «^ » в языках C++/Java/Python.
Для множества чисел S рассмотрим множество XOR-сумм всех возможных подмножеств S. Назовем это множество F(S).
Друг Ксони постоянно спрашивает у нее вопрос - "Если рассмотреть множество всех чисел, записанных в поддеревье вершины v (назовем ее Uv), то какое число во множестве F(Uv) будет k-е по возрастанию?". То есть, если взять все числа из поддеревья вершины v, рассмотреть все XOR-суммы их подмножества, то какое число в полученном множестве будет на k-ом месте по возрастанию? Если такого числа нет (k>∣F(Uv)∣), то Ксоня соответствует числу −1. Обратите внимание, что F(Uv ) – множество, а не мультимножество. То есть если одно число встречается несколько раз, то его нужно учитывать только один раз.
Также, иногда друг Ксони просит ее изменить одно из чисел в деревьях

Входные данные
Первая строка содержит два целых числа n,g (2≤n≤5⋅10^4, 0≤g≤7) — количество вершин в дереве и номер группы.Каждая из следующих n−1 строк содержит по два целых числа x(i ),y(i).(1≤x(i),y(i)≤n). Это означает, что в дереве проведено ребро между вершинами x(i) и y(i). 20) — массив a начальных чисел на вершинах дерева.Следующая строка содержит одно целое число q (1≤q≤5⋅10^4) — количество запросов.Каждая из следующих q строк описывает один запрос.Запросы на изменение числа в дереве имеют вид 1 x(i), y(i) (1≤x(i)≤n, 0≤y(i)<2^20). Такой запрос означает, что теперь на x(и)-й вершине записано число y(и ). Запросы другого типа имеют вид 2 v(i) k(i) (1≤v(i)≤n, 1≤k(i) )≤10^9). Такой запрос означает, что нужно найти k(i)-то по возрастанию число во множестве F(Uv(i)), где Uv(i)— множество чисел в поддеревье вершины v(i), а F(Uv(i)) - множество всех возможных XOR-сумм ее подмножеств. Если k(i)>∣F(Uv(i))∣, выведите −1.

Исходные данные
На каждый запрос второго типа выведите ответ в отдельной строке.

Заметка
Объяснение первого примера. Числа у вершин — a(i).

examples1.png


В первом запросе рассматривается поддерево вершины 2. Оно содержит числа 1,2,3.
F([1,2,3])=[0,1,2,3].
Во втором запросе рассматривается все поддерево. F([1,2,3,4])=[0,1,2,3,4,5,6,7].
После смены одного числа дерево выглядит так.

examples2.png

Теперь в поддеревье вершины 2 числа 1,2,4.
F([1,2,4])=[0,1,2,3,4,5,6,7].

Входные данные №1
5 0
1 2
1 5
2 3
2 4
4 2 3 1 2
7
2 2 4
2 1 2
2 2 3
1 3 4
2 5 1
2 2 8
2 1 5

Ответ №1
3
1
2
0
7
4

Миниатюры

   

0