Блэк & Уайт

Поймём, как может быть устроено остовное дерево. Рассмотрим отрезки вершин на окружности, которые последовательно соединены рёбрами. Каждый такой отрезок должен соединяться с центральной вершиной ровно одним ребром.

Будем решать задачу методом «Разделяй и властвуй». Рассмотрим отрезок вершин на окружности с номерами $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$). Рассмотрим на $$$[l, r]$$$ отрезки вершин, соединенных ребрами. Все отрезки, кроме самого левого и самого правого точно соединены с центральной вершиной ребром. Заметим, что для того, чтобы объединить два отрезка в «Разделяй и властвуй», достаточно для отрезка знать соединен ли его самый левый отрезок с центральной вершиной, и соединен ли его самый правый отрезок с центральной вершиной. Будем для каждого из $$$4$$$ типов отрезков хранить вектор, $$$i$$$-й элемент которого равен количеству способов выбрать ребра на отрезке, чтобы получить данный тип, и при этом среди выбранных рёбер было ровно $$$i$$$ белых. После этого, чтобы получить аналогичные вектора для объединения двух отрезков, нужно вычислить $$$O(1)$$$ свёрток. Для этого можно воспользоваться алгоритмом быстрого преобразования Фурье. В конце, нужно дополнительно учесть ребро, соединяющее вершины $$$n$$$ и $$$1$$$. Итоговая асимптотика — $$$O(n \cdot \log^2(n))$$$. Для того, чтобы узнать, какие именно свёртки нужно вычислить для пересчёта, можете посмотреть авторское решение.