Вентиляция

Подвесим дерево за одну вершину, запустим поиск в глубину. Для каждой вершины сохраним родителя pv, время входа tinv и время выхода toutv.

Заметим, что если вершина x является предком вершины y, то tinx ≤ tiny ≤ touty ≤ toutx.

Нужно ответить на запрос a, b. Если a не является предком b, то ответ — это pa, так как вершины b нет в поддереве вершины a, следовательно, туда спускаться не надо.

Если a является предком b, то ответ - это один из детей вершины a, а именно тот, в чьём поддереве находится b (то есть, tinans ≤ tinb ≤ toutb ≤ toutans). Заметим, что дети упорядочены по возрастанию tin и tout, значит, можно найти нужную вершину бинарным поиском.