K-я порядковая статистика между двумя вершинами дерева

Revision ru1, by mathAway, 2020-12-01 15:40:11

Задача: есть дерево, в каждой вершине которого записано число. Требуется отвечать на запросы (u,v,k) — найти k-ю порядковкую статистику на пути между вершинами u и v. Количество вершин и количество запросов <= 1e5. (https://www.spoj.com/problems/COT/).

Пока что не знаю, как решать эту задачу, но решал похожую: отвечать на запросы (u,k) — найти k-ю порядковую статистику в поддереве вершины u(https://www.spoj.com/problems/PT07J/). Там я перенумеровал все вершины таким образом, что задача свелась к нахождению порядковой статистики на отрезке массива, что решается персистентным деревом отрезков. Тут же я не нашёл способа, что и как можно перенумеровать, чтобы достичь подобного эффекта.

Есть идеи?

Tags дерево отрезков, структуры данных, порядковая статистика

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian mathAway 2020-12-02 14:57:16 24
ru1 Russian mathAway 2020-12-01 15:40:11 773 Первая редакция (опубликовано)