5217. LCA offline
Изначально имеется дерево, состоящее
только из корня (вершина с номером 1). Требуется научиться отвечать на
следующие запросы:
·
ADD
a b – подвесить вершину b за вершину a (гарантируется, что вершина a
уже существует).
·
GET
a b – вернуть LCA вершин a и b.
Вершины имеют номера от 1 до n.
В каждый момент времени у нас имеется одно дерево.
Вход. В первой строке содержится
количество запросов k. Следующие k строк содержат сами запросы.
Гарантируется, что число запросов каждого из типов не превосходит
500000.
Выход. Для каждого запроса типа GET
выведите в отдельную строку одно целое число – ответ на соответствующий запрос.
|
Пример
входа |
Пример
выхода |
|
9 ADD 1 2 ADD 1 3 ADD 2 4 GET 1 3 GET 2 3 GET 3 4 ADD 2 5 GET 4 5 GET 5 5 |
1 1 1 2 5 |
РЕШЕНИЕ
структуры
данных – Least Common Ancestor
Анализ алгоритма
Сведем задачу к
RMQ за время O(n). Препроцессинг RMQ
требует O(nlogn) по времени и памяти. Выполнение запроса GET будет производиться
за O(1).
Пример
Отобразим дерево,
построенное в примере. Выполним на нем несколько запросов.
Реализация
алгоритма
Таблицу RMQ будем строить в массиве mas. MAX – наибольшее
возможное количество вершин в дереве.
#define MAX 500010
#define LOGMAX 18
int mas[2*MAX][LOGMAX+1];
Дерево храним как граф в списке смежности g. Массивы Order, Height и First используются
для сведения задачи LCA к RMQ. Все поступающие запросы поместим в массив пар Query.
vector<int> g[MAX];
int Order[2*MAX], Height[2*MAX],
First[MAX];
В функции BuildRMQ по массиву a размера size
строим массив mas, для которого
mas[i][j] = arg min(ai, ai+1, …, ai+2^j-1)
void BuildRMQ(int *a, int size)
{
int i, j;
for (i = 0; i <= size; i++) mas[i][0] = i;
for (j = 1; 1 << j < size; j++)
for (i = 1; i + (1 << j) - 1 < size; i++)
if (a[mas[i][j - 1]] < a[mas[i + (1 << (j -
1))][j - 1]])
mas[i][j] =
mas[i][j - 1];
else
mas[i][j] =
mas[i + (1 << (j - 1))][j - 1];
}
Функция RMQ возвращает
минимум на отрезке (ai, ai+1, …, aj) за O(1).
int RMQ(int i, int j)
{
if (i > j) swap(i,j);
Находим
наибольшее k, для которого 2k не больше длины интервала запроса, то есть значения j – i + 1.
Или то же самое, что k = 
.
int k = 0;
while ((1 << (k + 1)) <= j - i + 1) k++;
int res = mas[i][k];
if (Height[mas[j - (1<<k) + 1][k]] <
Height[res])
res = mas[j -
(1<<k) + 1][k];
return res;
}
Функция dfs реализует обход дерева в глубину.
Порядок обхода вершин дерева сохраняем в массиве Order, их высоты – в массиве Height (с фиксированием времени захода в вершину и возвращения в нее). Вызов dfs(v,
p, h) означает, что стартует поиск в глубину из вершины v, имеющей высоту h, причем непосредственным предком v является p. Время первого входа в вершину v занесем в First[v].
void dfs(int v, int p = 0, int h = 0)
{
Height[time] = h;
Order[time] = v;
First[v] = time++;
for(int i = 0; i <
g[v].size(); i++)
{
int to = g[v][i];
if (to != p)
{
dfs(to, v, h +
1);
Order[time] =
v;
Height[time++]
= h;
}
}
}
Функция Init_LCA совершает препроцессинг LCA. Запускаем обход дерева в
глубину, в котором будут
построены все вспомогательные массивы. Выполняем препроцессинг RMQ по массиву
высот Height, который содержит высоты вершин при их обходе.
void Init_LCA(void)
{
memset(First,0,sizeof(First));
time = 1; dfs(1);
BuildRMQ(Height,time);
}
Функция LCA возвращает
вершину дерева, являющуюся LCA(i, j).
int LCA(int i, int j)
{
int index = RMQ(First[i],First[j]);
return Order[index];
}
Основная часть программы. Читаем входное дерево, заполняем
структуру g. Запросы собираем в массив пар Query.
scanf("%d\n",&k);
for(i = 0; i <
k; i++)
{
scanf("%s %d %d\n",op, &a,&b);
if (op[0] == 'A')
g[a].push_back(b);
else Query.push_back(make_pair(a,b));
}
Сводим задачу LCA к RMQ.
Init_LCA();
Последовательно обрабатываем запросы.
Выводим ответ на каждый из них за O(1).
for(i = 0; i <
Query.size(); i++)
printf("%d\n",LCA(Query[i].first,Query[i].second));