Задача: есть дерево, в каждой вершине которого записано число. Требуется отвечать на запросы (u,v,k) — найти k-ю порядковкую статистику на пути между вершинами u и v. Количество вершин и количество запросов <= 1e5.Оригинал
Пока что не знаю, как решать эту задачу, но решал похожую: отвечать на запросы (u,k) — найти k-ю порядковую статистику в поддереве вершины u(Оригинал). Там я перенумеровал все вершины таким образом, что задача свелась к нахождению порядковой статистики на отрезке массива, что решается персистентным деревом отрезков. Тут же я не нашёл способа, что и как можно перенумеровать, чтобы достичь подобного эффекта.
Есть идеи?
С помощью heavy-light декомпозиции задача сводится к "найти k-ю порядковую статистику в массиве на объединении log n отрезков". Это решается так же, как и обычная k-я порядковая статистика, только теперь вместо параллельного запуска из двух вершин, запускаемся из 2 * "кол-во отрезков, на которые разбился путь" вершин.
UPD. И правда, снизу предложено решение куда лучше
Окей, прочитаю что за она, на это ещё нужно время. Спасибо!
Зачем тут HLD? Можно в персистентном ДО хранить все числа на пути от корня до вершины, для вершины $$$i$$$ обозначим такое дерево как $$$tree_i$$$.
Тогда ответ считается как спуск по $$$tree_v + tree_u - 2 \cdot tree_{lca(v, u)} + number\,in\,vertex\,lca(v, u)$$$.
Код очень похож на подсчет на отрезке, где за $$$tree_i$$$ мы обозначаем дерево со всеми числами на префиксе длины $$$i$$$, и спуск происходит по $$$tree_r - tree_{l - 1}$$$.
Блин, а я ведь мыслил очень близко! Но если мы для каждой вершины будем хранить все числа на пути от корня до неё, то не будет ли такое решение потреблять n^2 памяти? Если сравнивать с использованием пдо для нахождения к-й порядковой статистики на отрезке, то там мы строим его так: создаём массив x размера количества различных элементов в исходном массиве, а затем бежим слева направо по этому исходному массиву и прибавляем единичку в соответствующей позиции массива x, только этот массив хранится в виде до и у нас есть все его версии, т.е. пдо. Почему объём памяти куда меньше, чем мне кажется? Если брать, к примеру случай дерева, как последовательно связанных вершин, а корнем является вершина 1.
Это будет $$$O(n \log n)$$$ памяти.
Пишется аналогично задаче на массиве, просто вместо $$$tree_i = add(tree_{i - 1}, a_i)$$$ (тут $$$a_i$$$ — элемент массива) получается $$$tree_i = add(tree_{parent_i}, a_i)$$$ (тут $$$a_i$$$ — число в вершине, $$$parent_i$$$ — предок в дереве)
Всё, я наконец понял, спасибо :) Я на некоторое время забыл, что обновление в пдо добавляет лишь логарифм вершин.
Автокомментарий: текст был обновлен пользователем mathAway (предыдущая версия, новая версия, сравнить).