<ПРЕД Задача:
СЛЕД>
Задачу решили 148 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

LCA problem

Time limit = 4 секунд(ы)

Memory limit = 40 Mb

Описание задачи.

Реализовать быстрый поиск ближайшего общего предка двух заданных элементов в дереве.

Вход.

В первой строке дано количество узлов дерева N, не считая корневого узла. Затем идут N строк с описанием ребер дерева (в каждой строке указан идентификатор вершины, а затем идентификатор его родителя).

Идентификаторы узлов лежат в диапазоне 0 до N. Узел 0 является корнем дерева.

Затем идёт строка с числом запросов M. Затем идут M строк с описанием запросов.

Каждый запрос содержит идентификаторы двух узлов. Необходимо найти идентификатор их ближайшего общего предшественника.

N ≤ 400000, M ≤ 400000.

Выход. Выход должен состоять из M строчек, в которых даны ответы на запросы.

Вход#1
10
1 0
2 1
3 1
4 2
5 2
6 3
7 3
8 6
9 7
10 7
4
8 10
2 5
4 5
6 9
Выход#1
3
2
2
3

Автор:
Описание и тесты -- Вячеслав Семененко
15 мая 2007

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 3.92.74.105