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

Мой вариант рассмотрите?

Я так понял вы хотите хранить для каждой вершины список из logn центроидов, с центроидом хранить ДО, и в каждом за log делать запрос?

Да

И выбирать максимум

ДО, где храняться длины путей до центра, максимум на отрезке и прибавляемое. А листья - вершины в нужном порядке обхода

Поиск сводится к 2 или 3 запросам к до

Я вас понял. Подытожу, думаю кому то пригодится.
Давайте для каждого центроида будем хранить дерево отрезков из n элементов, где n — размер поддерева. Значением i-ой вершины будет путь от центроида до i-ой вершины path[i].
Вершины будем хранить похожим способом, как в Euler tour tree (запишем каждую вершину при входе в нее). Тогда все поддеревья i будут являться отрезками [i, i + size], где size - размер поддерева вершины i.
Запрос максимального пути, проходящий через v разобьем на два: максимальный путь проходящий через какой то центроид c и v, и максимальный путь из c в вершину из другого поддерева, не равное тому, в котором лежит v.
Отвечаем на запрос максимального пути из c через v: для этого возьмем максимум из path[i] в поддереве v
Отвечаем на запрос максимального пути из c в вершину из другого поддерева: возьмем максимум из path[i] на всем ДО, кроме отрезка, равный поддереву вершины-ребенка c, в котором вершина v.
Обновляем вес v: фиксируем центроид c, находим в дереве под-отрезок, соответствующий поддереву v, везде прибавляем к path[i] какое то delta за log n с ДО с массовыми операциями.
Итоговая асимптотика: log^2 n на запрос, так как перебираем log n центроидов, и в каждом ДО делаем запросы за log n
Предпосчет: nlogn. У нас log n уровней, на каждом уровне надо построить ДО для n вершин. ДО умеем строить за O(N) для уже посчитанного массива path[i]

Спасибо)

Есть такая задача.
https://leetcode.com/problems/sum-of-all-subset-xor-totals/
Суть - у массива найти XOR всех его подмножеств.
Есть наивный подход - находишь собственно все подмножества и вычисляешь у каждого из них его XOR.

Есть же ещё другой подход https://leetcode.com/problems/sum-of-all-subset-xor-totals/discuss/1211177/Simple-trick-oror-4-lines-of-code-oror-Explained!!, который я не могу понять, хотя объяснения и даны.
Там решение в O(N):

int subsetXORSum(vector<int>& arr) {
        int n = arr.size(), res = 0;
        for (int i=0; i < n; ++i)
            res |= arr[i];
        return res * (1<< n-1);
}

Кто-нибудь может на пальцах объяснить как они к такому пришли?

Пусть какой-то бит встречается хотя бы в одном числе, тогда этот бит будет равен 1 в 2^(n-1) xor'ах: из чисел в которых бита нет мы можем взять любое подмножество, из чисел в которых он есть только подмножество нечетного размера, которых ровно половина

Нет, не понятно ещё больше.

>Пусть какой-то бит встречается хотя бы в одном числе
А зачем нам это надо понимать? То что бит встречается хотя бы в одном числе. Что это даст в итоге?

Позволит посчитать ответ отдельно для случая когда встречается и когда не встречается (0)

А есть связь с каким-нибудь каналом ютубовским, что человек мог сделать детальный разбор на решение этой задачи?
Эта задача из русскоязычных ещё никем не рассматривалась.

Это не ко мне🤷🏻‍♂

This is spam protection. You have 30 seconds to press the button or you will be banned!

За какой срок реально стать красным на кф?

рекурсивно мб?

Всмысле проверить, является ли заданное число суммой каких-либо чисел образованных из одной единственной цифры?

какие ограничения на x?