хммм. Можно даже так. Будем идти обходом в ширину по маскам, где ребро - это прибавление одного бита, запускаемся от нулевой маски. Очевидно, что если парсоч для данной маски уже не полный - значит, если мы будем добавлять биты, мы полный парсоч не получим. То есть, запускаемся только от тех масок, где получен уже полный парсоч, и в них ищем увеличивающую цепь. Асимптотику как посчитать в таком варианте решения я не знаю, но это в разы быстрее чем для каждой маски строить парсоч - во-первых, мы отсекаем явно невалидные маски, во-вторых, мы ответ достраиваем, а не строим с самого начала.

По скольку нам надо вывести не само дерево, а только число вершин в нём, то можно всё сделать попроще.

Рассмотрим некоторый лист нашего дерева. К этому листу от ближайшей к нему развилки (развилка это вершина степени >= 3) ведёт цепочка. Найдём длинну этой цепочки. Alias уже почти написал как. Зафиксируем произвольно начало его кишки, переберём все остальные вершины в качестве конца. И из всех 'x' - расстояний до кишки выберем минимальное. Это и будет расстояние до ближайшей развилки. Добавим его к ответу. После чего нашу вершину, вместе с цепочкой ведущей к ней, удалим из дерева. Тоесть просто больше никогда не будем её рассматривать в качестве конца кишки. И так сделаем для каждой вершины.

Получаем 2 вложенных фора (перебираем вершину и для каждой вершины перебираем конец кишки) и одна формула рассчёта расстояния до кишки внутри. Пишется 5 минут.