\begin{tutorial}{Опять деревья...}

\textbf{ Подгруппа 1. } 

Для начала заметим, что если XOR чисел в дереве не равен нулю, то ответ $0$. Посмотрим на какое-то ребро. При удалении его, дерево разбивается на поддерево и наддерево. Если XOR в поддереве не равен нулю, то мы не сможем дальше удалить ребра так, чтобы XOR в каждой компоненте был равен нулю. При этом если XOR в поддереве равен нулю, то и в наддереве он тоже равен нулю, и удаление этого ребра никак не повлияет на остальные ребра, поэтому ответ~--- это $2^{\mathrm{cnt}}$, где $\mathrm{cnt}$~--- это количество поддеревьев с XOR 0, кроме всего дерева. Асимптотика $\mathcal{O}(n)$.

\textbf{ Подгруппа 2. } 

Достаточно перебрать все множества ребер и проверить красивое оно или нет. Асимптотика $\mathcal{O}(2^n \cdot n)$.

\textbf{ Подгруппа 3. } 

Сделаем $\mathrm{dp}[v][x]$ ~--- количество вариантов выбрать множество ребер из поддерева этой вершины, включая ребро из вершины $v$ в предка, так, чтобы отрезанные вершины в поддереве имели XOR равный $x$. Чтобы пересчитать $\mathrm{dp}$ нужно сначала посчитать XOR свертку значений $\mathrm{dp}$ сыновей. XOR свертка массивов $a$ и $b$ длины $2^k$ ~--- это массив $c_i = \sum a_j \cdot b_{j \oplus i}$. Ее пока что будем считать за произведение размеров массивов. После $XOR$ свертки всех сыновей, мы должны обработать вариант удаления ребра из $v$ в ее предка. Для этого переберем какой был $x$ и если $\mathrm{xor\_subtree}[v] \oplus x \in b$, то нужно прибавить $\mathrm{dp}[v][x]$ к $\mathrm{dp}[v][0]$. Таким образом это решение работает за $\mathcal{O}(n \cdot 32^2)$.

\textbf{ Подгруппа 4. }  

Нам нужно посчитать количество разбиений массива на подотрезки, где XOR в каждом подотрезке лежит в $b$. Для этого будем идти слева направа по массиву и поддерживать $\mathrm{dp}[i]$ ~--- количество разбиений префикса длины $i$ на подотрезке. Пересчет $\mathrm{dp}[i] = \sum \mathrm{dp}[j]$, где $\mathrm{pref}[i] \oplus \mathrm{pref}[j - 1] \in b$, где $\mathrm{pref}[i] = \oplus a_j$ по $j \leq i$. Такой пересчет оптимизируется с помощью \verb|std::map| и мы получаем решение за $\mathcal{O}(n \log n \cdot k)$.

\textbf{ Подгруппы 5--7. }  

Выберем базис из множества $b$ и будем хранить $\mathrm{dp}$ из третьей группы в этом базисе. Из-за перехода в другой базис немного усложняется реализация, а в остальном $\mathrm{dp}$ остается прежней. Также, есть решение без базиса, но оно не оптимизируется до полного решения. Решение работает за $\mathcal{O}(n \cdot 4^{k})$ из-за того, что одна XOR свертка работает за $4^k$.

\textbf{ Подгруппы 8, 9. }  

Будем делать XOR свертку алгоритмом Адамара. Получаем асимптотику $\mathcal{O}(n \cdot 2^k \cdot k)$. Также стоит отметить, что решения без Адамара могли пройти эти группы, если использовать некоторые неасимптотические оптимизации, которые на самом деле могут быть асимптотическими.

\textbf{ Подгруппа 10. }  

Мы хотим избавиться от домножения на $k$. Одна XOR свертка адамаром выглядит так: считаем преобразование Адамара от обоих массивов, затем считаем поточечное умножение и делаем обратное преобразование Адамара. Вместо того, чтобы хранить $\mathrm{dp}[v][x]$, будем хранить $\mathrm{hadamard}(\mathrm{dp}[v][x])$, то есть преобразование Адамара. Его формула такая: $\mathrm{hadamard}(a)[i] = \sum a_j \times (-1)^{\mathrm{popcount}(i \,\&\, j)}$. Тогда свертка делается за $\mathcal{O}(2^k)$ поточечным произведением. Теперь возникает сложность со вторым пересчетом, где мы хотели посчитать значение $\mathrm{dp}[v][x]$ в каких-то точках $x$ и прибавить это к $\mathrm{dp}[v][0]$. 

Начнем с первого шага. Нужно посчитать $\sum \mathrm{dp}[v][b_i \oplus \mathrm{xor\_subtree}[v]]$. Стоит отметить, что если $\mathrm{xor\_subtree}[v]$ не раскладывается по базису, то такой пересчет делать не нужно. Для начала посчитаем такую сумму в предположении, что $\mathrm{xor\_subtree}[v]$ = 0. Пусть $p$~--- массив размера $2^k$, где на позициях $b_i$ записаны 1, а на остальных позициях нули. Тогда сумма, которую нужно посчитать~--- это нулевой элемент XOR свертки $\mathrm{dp}[v]$ и $p$. Саму свертку $\mathrm{dp}[v]$ и $p$ мы посчитать не можем, но мы можем посчитать $q = \mathrm{hadamard}$(свертка $\mathrm{dp}[v]$ и $p$), поскольку это поточечное произведение $\mathrm{hadamard}(\mathrm{dp}[v])$ и $\mathrm{hadamard}(p)$, а $\mathrm{hadamard}(p)$ мы можем посчитать один раз в начале программы. Теперь нам интересен нулевой элемент от обратного преобразования $q$, а это просто $(\sum q_i) / 2^k$. Теперь вспомним, что у нас есть $\mathrm{xor\_subtree}[v]$, но чтобы его учесть, достаточно добавить в свертку $\mathrm{dp}[v]$ и $p$, массив, где единица стоит только на позиции $\mathrm{xor\_subtree}[v]$. $\mathrm{hadamard}$ от такого массива вычисляется за $\mathcal{O}(2^k)$ по определению. Таким образом мы за $\mathcal{O}(2^k)$ посчитали нужную сумму.

Теперь нужно посчитать новый $\mathrm{hadamard}(\mathrm{dp}[v])$ после такого, как мы бы прибавили к $\mathrm{dp}[v][0]$ посчитанную сумму. Но по определению преобразования Адамара мы можем найти коэффициенты с которыми учтется прибавленная сумма к старому значению $\mathrm{hadamard}(\mathrm{dp}[v])$.

Таким образом в этом решении делать преобразование Адамара в явном виде нужно только для вычисления $\mathrm{hadamard}(p)$, а в остальном мы явно вычисляем нужны коэффициенты по определению и получаем решение $\mathcal{O}(n \cdot 2^k)$.


\end{tutorial}
