LCA-сумма

Для каждой вершины дерева посчитаем, для скольких подмножеств она будет являться LCA и умножим это количество подмножеств на номер самой вершины. Просуммируем данную величину по всем вершинам и получим ответ.

Чтобы посчитать, для какого количества подмножеств эта вершина является LCA, можно использовать dfs, который для каждой вершины будет возвращать пару значений:

1. количество подмножеств, состоящих из вершин, лежащих не выше текущей, для которых:

   - либо данная вершина является LCA
   - либо кто-то из ее потомков является LCA
2. размер поддерева, с учетом этой вершины.

Таким образом, для листов значения этой пары равны {1, 1} — так как лист является LCA только для себя самого, и его поддерево состоит только из 1 вершины — самого листа.

Получим, что некоторая вершина-родитель, вызывая dfs для всех своих прямых потомков, получает количество подмножеств, для которых уже известно, кто LCA (соответственно, вершина-родитель уже не LCA), а также размер их поддеревьев.

Пусть $$$num$$$ — сумма размеров поддеревьев по всем прямым потомкам, то есть количество всех вершин, которые расположены ниже текущей.

А $$$sum$$$ — сумма значений количеств подмножеств по всем прямым потомкам, для которых известно LCA.

Тогда из них можно выбрать $$$2^{num} - 1$$$ различных непустых подмножеств (каждый элемент мы либо берем, либо нет, поэтому варианты выбора подмножеств можно представить как двоичные числа длины num).

При этом, для $$$sum$$$ из них текущая вершина-родитель LCA являться не будет, так как им уже являются другие, лежащие ниже, вершины.

Получим, что текущая вершина будет являться LCA для $$$2^{num} - 1 - sum$$$ подмножеств. Зафиксируем это значение в массиве ответа.

Теперь для $$$2^{num} - 1$$$ подмножеств известно, какая вершина для них является LCA. Вернем это число как первое значение пары.

Как второе значение вернем просто $$$num + 1$$$, так как мы учитываем текущую вершину.

Вызвав такой dfs от корня дерева, мы получим массив, показывающий для каждой вершины, для скольких подмножеств она будет являться LCA.