Гранди на деревьях

Дерево в условии задачи про игру встречается постоянно, а правило вычисления зависит не от него, а от того, что делает ход.

Ход двигает фишку

Фишка стоит в вершине, ход переставляет её в ребёнка. Позиция — это вершина, ходы из неё ведут в детей, и работает обычное определение:

$$g(v) = \mathrm{mex}\ \{\, g(c) : c \text{ — ребёнок } v \,\}.$$

Листья получают ноль. Если фишек несколько, позиция — сумма игр, и значение равно XOR значений их вершин.

Ход рубит ребро

Ход разрубает ребро, и всё, что отделилось от корня, отваливается. Теперь ветки разных детей независимы: рубка в поддереве одного ребёнка не касается другого. Значит, позиция — сумма игр, и

$$g(v) = \bigoplus_{c \text{ — ребёнок } v} \bigl(g(c) + 1\bigr).$$

Единица — это само ребро в ребёнка: его тоже можно разрубить, и тогда ветка исчезнет целиком. Строгая формулировка: стебель длины 1 с прикреплённой игрой ценности $g$ имеет ценность $g + 1$. В теории Hackenbush это «принцип двоеточия».

for (int i = n - 1; i >= 0; i--) {          // порядок, обратный обходу
    int v = order[i], value = 0;
    for (int c : children[v]) value ^= grundy[c] + 1;
    grundy[v] = value;
}

Обход пишите без рекурсии. Цепочка из ста тысяч вершин — обычное дело, а стек кончается на десятках тысяч.

Чем эти правила отличаются на практике

	двигаем фишку	рубим ребро
формула	mex по детям	XOR из $g(c)+1$
лист	$0$	$0$
цепочка длины $k$ от корня	$g = 0$ или $1$ по чётности	$g = k$
звезда из $k$ лучей	$1$	$k \bmod 2$

Последняя строка — хороший тест: если ваша программа на звезде из трёх лучей даёт единицу в игре с рубкой, правило перепутано.

Прибавление единицы не XOR-линейно

Соблазнительно думать, что $g(c) + 1$ ведёт себя как XOR с константой, и построить на этом быстрый пересчёт «а что будет, если значение поддерева изменится». Это неверно:

$$(1 \oplus 2) + 1 = 4, \qquad (1 + 1) \oplus (2 + 1) = 1.$$

Поэтому задачи вида «посчитать все выигрышные рубки» не решаются одним числом на вершину: изменение приходится честно поднимать по пути к корню. Это $O(n \cdot \text{глубина})$, и ограничения в таких задачах обычно маленькие именно поэтому.

Перевешивание за другой корень

Если нужен ответ для каждого корня, считать заново $n$ раз — $O(n^2)$. Стандартный приём: посчитать значения при корне в первой вершине, а потом спуститься от корня, поддерживая «значение вершины со стороны родителя»:

$$up(c) = \Bigl(\, up(v) \ \oplus \bigoplus_{d \ne c} (g(d) + 1) \Bigr) + 1,$$

здесь $d$ пробегает остальных детей $v$, а $up(v)$ — вклад всего, что висит на $v$ сверху. XOR по всем детям, кроме одного, берётся как «общий XOR, из которого убрали слагаемое» — XOR сам себе обратен, поэтому убрать легко. Ответ для корня $c$ — это $up(c) \oplus \bigoplus_{\text{дети}} (g(\cdot) + 1)$.

Смежное: функция Гранди, сумма игр, принцип слияния.