K-я порядковая статистика между двумя вершинами дерева
Difference between ru1 and ru2, changed 24 character(s)
Задача: есть дерево, в каждой вершине которого записано число. Требуется отвечать на запросы (u,v,k) &mdash; найти k-ю порядковкую статистику на пути между вершинами u и v. Количество вершин и количество запросов <= 1e5. [Оригинал](https://www.spoj.com/problems/COT/).

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

Есть идеи?

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 Первая редакция (опубликовано)