Гра — це просто дерево «І-АБО». Фішка ніколи не повертається у відвідану вершину, а в дереві це означає, що вона просто йде простим шляхом із . Тому підвісимо дерево за : перший гравець обирає сина, другий — онука, і так далі, доки не впремося в лист. Перемагає другий, якщо лист активний.
Позначимо \mathrm{val}(v, p) — «чи виграє перший гравець», якщо фішка щойно прийшла у , розглядається лише піддерево , а каже, хто зараз ходить: p = 0 — перший (він хоче неактивний лист), p = 1 — другий (хоче активний). Тоді
де пробігає синів. Тобто на парних рівнях стоїть АБО (перший обирає найкраще для себе), на непарних — І (другий губить усе, де в нього є вибір). Відповідь на запит:
Далі — питання техніки: довільна, листки перемикаються, запити онлайн.
Підвішуємо один раз. Зафіксуємо корінь (будь-яку нелистову вершину) і будемо тримати «низхідні» значення \mathrm{down}(v, p) — значення піддерева . Для запиту в потрібні ще й «висхідні» \mathrm{up}(s, p) — значення решти дерева, якщо дивитися з вгору:
де — батько (а якщо у цій ролі виявляється листом, то \mathrm{up} = \neg\,\mathrm{active}(u)). Вилучення одного сина з АБО/І робиться миттєво, якщо тримати не самі кон'юнкції, а лічильники: скільки синів мають \mathrm{down}(c,1) = 1 і скільки мають \mathrm{down}(c,0) = 0.
Головне спостереження. Подивіться на рекурсію уважно: \mathrm{val}(v,0) залежить лише від \mathrm{val}(h,1), а \mathrm{val}(v,1) — лише від \mathrm{val}(h,0). Тобто підйом на один рівень міняє парність місцями, і вздовж ланцюжка вершин ролі АБО та І чергуються. А ще обидві операції коротко замикаються: щойно на кроці-АБО якийсь бічний син дає одиницю, усе вище вже одиниця; щойно на кроці-І якийсь бічний син дає нуль, усе вище вже нуль.
Назвемо вершину ланцюжка вирішальною (для даної парності), якщо саме на ній відбувається таке коротке замикання. Тоді значення на вершині ланцюжка визначає найближча зверху вирішальна вершина — а якщо такої немає, значення просто приходить із нижнього кінця ланцюжка, тобто з листа.
Структура даних. Розкладемо дерево важко-легкою декомпозицією. Для кожного ланцюжка і кожної з двох парностей тримаємо впорядковану множину позицій вирішальних вершин у цьому ланцюжку. Тоді:
запит «яке значення, якщо увійти в ланцюжок на позиції » — це lower_bound у множині: якщо щось знайшлося, відповідь дає парність відстані до цієї вершини, інакше — значення нижнього кінця;
підйом із до кореня проходить \mathcal{O}(\log n) ланцюжків, у кожному одна така операція.
Перемикання листка змінює лише на шляху до кореня, і завдяки короткому замиканню — лише доти, доки значення справді змінюються. Практично це означає перерахунок лічильників у \mathcal{O}(\log n) вершинах-стиках легких ребер і відповідні вставки/вилучення у множинах.
Разом — \mathcal{O}\bigl((n + q\log n)\log n\bigr), чого вистачає при n, q \le 5 \cdot 10^5. Розв'язок повністю онлайновий, тож проходить і режим m = 1; не забудьте лише розшифровувати номер вершини за формулою з умови й оновлювати лічильник після кожного запиту — у тому числі після запиту на перемикання.