Гра на дереві#534

Гра на дереві

2 секунди
256 мегабайтів
Дуже складна

Дано дерево на вершинах. Кожен листок (тобто вершина степеня ) має статус: активна або неактивна. Спочатку всі листки неактивні.

Дано запитів двох типів:

Гра: є фішка, що початково розташована у вершині . Двоє гравців ходять по черзі, починає перший гравець. На кожному ході гравець переміщає фішку у невідвідану сусідню вершину. Гра закінчується, коли фішка опиняється у вершині, з якої немає куди ходити (тобто всі сусідні вершини вже відвідані — це обов'язково листок графа). Другий гравець перемагає, якщо фішка завершила хід в активній вершині; інакше перемагає перший.

Онлайн-режим. Якщо вхідний параметр m = 1, то у кожному запиті замість справжнього номера вершини подається зашифроване число.

Розглянемо запит одного з двох типів:

Нехай — лічильник, спочатку рівний . Для кожного запиту число дешифрується у справжній номер вершини за формулою

v = ((x - 1 + \mathit{acc}) \bmod n) + 1.

Тобто:

Після кожного запиту лічильник оновлюється:

Якщо m = 0, то запити не шифруються. У такому випадку в запиті 1 v число є листком, статус якого потрібно змінити, а в запиті 2 v число є початковою вершиною гри.

Вхідні дані

У першому рядку задано три цілі числа , та (3 \le n \le 5 \cdot 10^5, 1 \le q \le 5 \cdot 10^5, m \in \{0, 1\}).

У наступних n - 1 рядках задано ребра дерева: по два цілі числа u_i та v_i (1 \le u_i, v_i \le n, u_i \ne v_i).

У наступних рядках задано запити: тип t \in \{1, 2\} та аргумент (1 \le x \le n). Якщо m = 1, то є зашифрованим значенням.

Вихідні дані

Для кожного запиту другого типу виведіть в окремому рядку одне число: , якщо переможе перший гравець, або , якщо переможе другий.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

У першому прикладі дерево — зірка з вершиною у центрі та листочками . Спочатку всі листочки неактивні: на запит 2 1 перший гравець робить єдиний хід у будь-який з листочків, і фішка зупиняється у неактивному листочку — перший виграє, відповідь . Після трьох запитів типу , що активують усі листочки, на повторний запит 2 1 куди б перший не пішов, фішка опиняється в активному листочку — перемагає другий, відповідь .

У другому прикладі дерево має форму Y: вершина з'єднана з вершинами , та з вершиною , до якої прикріплений листочок . Запит 2 3 означає, що дерево підвішується за вершину . До активації будь-яких листочків перший гравець може дістати неактивний листочок з вершини за один хід (наприклад, у ) — відповідь . Після активації листочків , , всі три можливі шляхи з закінчуються в активному листочку, тож перший не уникне програшу — відповідь .

У третьому прикладі продемонстровано онлайн-режим (m = 1) на тому самому дереві, що й у першому прикладі. Початкове значення \mathit{acc} = 0, тож перший зашифрований запит 2 1 декодується у запит 2 1 і дає відповідь , після чого \mathit{acc} = 1. Наступний зашифрований запит 1 1 декодується як 1 2 (бо ((1 - 1 + 1) \bmod 4) + 1 = 2), активуючи листочок , і потім \mathit{acc} = (1 + 2) \bmod 4 = 3. Аналогічно 1 4 декодується як 1 3 (активує листочок , \mathit{acc} = 2), а 1 2 — як 1 4 (активує листочок , \mathit{acc} = 2). Останній зашифрований запит 2 3 декодується як 2 1 і повертає .

Оцінювання

  1. ( бали): n, q \le 1000, m = 0;

  2. ( балів): листок ніколи не змінює статус з активного на неактивний, s = 1, m = 0;

  3. ( балів): листок ніколи не змінює статус з активного на неактивний, фішка на початку гри в кожному запиті знаходиться у першій вершині, m = 1;

  4. ( бал): m = 0, існує ціле k \ge 1 таке, що n = 2^k - 1, а ребра дерева мають вигляд (i, \lfloor i / 2 \rfloor) для всіх 2 \le i \le n.

  5. ( балів): лише вершина має степінь більше ніж , m = 0;

  6. ( балів): s = 1, m = 0;

  7. ( балів): n \le 10^5, m = 0;

  8. ( балів): без додаткових обмежень.