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

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

Есть идеи?