Codeforces Round 950 (Div. 3) |
---|
Закончено |
Яся гуляла по лесу и совершенно случайно нашла дерево на $$$n$$$ вершинах. Дерево — это связный неориентированный граф, в котором отсутствуют циклы.
Рядом с деревом девочка нашла древний манускрипт, на котором записаны $$$m$$$ запросов. Запросы бывают двух видов.
Первый вид запросов описывается числом $$$y$$$. Вес каждого ребра в дереве заменяется на побитовое исключающее «ИЛИ» веса этого ребра и числа $$$y$$$.
Второй вид описывается вершиной $$$v$$$ и числом $$$x$$$. Яся выбирает вершину $$$u$$$ ($$$1 \le u \le n$$$, $$$u \neq v$$$) и мысленно проводит в дереве двунаправленное ребро веса $$$x$$$ из $$$v$$$ в $$$u$$$.
Затем Яся находит простой цикл в получившемся графе и считает побитовое исключающее «ИЛИ» от всех рёбер на нём. Она хочет выбрать такую вершину $$$u$$$, чтобы посчитанное значение было максимально. Это посчитанное значение и будет ответом на запрос. Можно показать существование и единственность такого цикла в указанных ограничениях (независимо от выбора $$$u$$$). Если ребро между $$$v$$$ и $$$u$$$ уже существовало, простым циклом будет путь $$$v \to u \to v$$$.
Обратите внимание, что запрос второго типа выполняется мысленно, то есть дерево после него никак не меняется.
Помогите Ясе ответить на все запросы.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Далее следуют описания наборов.
В первой строке каждого набора даны целые числа $$$n$$$, $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — количество вершин в дереве и количество запросов.
В следующих $$$n - 1$$$ строках каждого набора даны целые числа $$$v$$$, $$$u$$$, $$$w$$$ ($$$1 \le v, u \le n$$$, $$$1 \le w \le 10^9$$$) — концы некоторого ребра в дереве и его вес.
Гарантируется, что заданный набор рёбер образует дерево.
В следующих $$$m$$$ строках каждого набора описаны запросы:
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. То же самое гарантируется для $$$m$$$.
Для каждого набора входных данных выведите ответы на запросы второго типа.
23 71 2 13 1 8^ 5? 2 9^ 1? 1 10^ 6? 3 1? 2 95 61 2 7773 2 28124 1 165 3 1000000000^ 4? 3 123? 5 1000000000^ 1000000000? 1 908070? 2 1
13 15 11 10 1000000127 2812 999756331 999999756
38 48 6 36 3 42 5 47 6 27 1 104 1 45 1 2^ 4^ 7? 7 8? 4 105 63 1 42 3 94 3 65 2 10? 5 7^ 1^ 8? 4 10? 1 9? 3 64 22 1 44 3 52 3 4^ 13? 1 10
14 13 13 8 11 11 10
Название |
---|