Безумные расстановки

Докажем, что ответ не зависит от дерева. Введем переменную $$$h_v$$$, равную исключающему ИЛИ значений на пути от вершины $$$v$$$ до корня (за корень можно взять любую вершину). Тогда исключающее ИЛИ на пути между вершинами $$$u$$$ и $$$v$$$ равно $$$h_u \oplus h_v$$$.

По значениям $$$h_v$$$, для любого дерева и корня $$$r$$$, веса ребер восстанавливаются однозначно, если $$$h_r = 0$$$. Таким образом, мы просто свели задачу к подсчету правильных массивов $$$h$$$.

Зафиксируем границу, которая разделяет пути, на которых исключающее ИЛИ равно $$$0$$$, и пути, на которых исключающее ИЛИ равно $$$1$$$.

Тогда у нас есть условия $$$h_{u_i} \oplus h_{v_i} = q_i$$$ (где $$$q_i = 0$$$ для путей слева от границы, и $$$q_i = 1$$$ для путей справа от границы), и нужно посчитать число массивов, подходящих под такие ограничения.

За $$$O(n + m)$$$ это можно сделать алгоритмом, подобным покраске графа в два цвета. Тогда решение будет работать за $$$O(m \cdot (n + m))$$$. Чтобы оптимизировать это решение дальше, предлагается воспользоваться техникой «разделяй и властвуй». Будем делать аналогично алгоритму Dynamic Connectivity. Когда идем в левую половину отрезка, добавляем в DSU правую половину с весами $$$1$$$. Когда идем в правую половину, добавляем в DSU левую половину с весами $$$0$$$.

Таким образом, время составит $$$O(m \log^2)$$$, а также может быть соптимизировано до $$$O(m \log)$$$ используя обход в глубину и явное сжатие графа вместо DSU с откатами.