3299. Общий предок - 2

Задано подвешенное дерево, содержащее n (1 ≤ n ≤ 10⁵) вершин, пронумерованных от 0 до n – 1. Требуется ответить на m (1 ≤ m ≤ 10⁷) запросов о наименьшем общем предке для пары вершин.

Запросы генерируются следующим образом. Заданы числа a₁, a₂ и числа x, y и z. Числа a₃, ..., a_2m генерируются следующим образом:

a_i = (x * a_i-2 + y * a_i-1 + z) mod n

Первый запрос имеет вид (a₁, a₂). Если ответ на (i – 1)-ый запрос равен v, то i-ый запрос имеет вид ((a_2i-1 + v) mod n, a_2i).

Вход. Первая строка содержит два числа n и m. Корень дерева имеет номер 0. Вторая строка содержит n – 1 целых чисел, i-е из этих чисел равно номеру родителя вершины i. Третья строка содержит два целых числа в диапазоне от 0 до n – 1: a₁ и a₂. Четвертая строка содержит три целых числа: x, y и z, эти числа неотрицательны и не превосходят 10⁹.

Выход. Выведите сумму номеров вершин – ответов на все запросы.

Пример входа 1	Пример выхода 1
3 2 0 1 2 1 1 1 0	2
Пример входа 2	Пример выхода 2
1 2 0 0 1 1 1	0

РЕШЕНИЕ

LCA – двоичный подъем

Анализ алгоритма

В задаче следует реализовать запросы о наименьшем общем предке для пар вершин. Дерево задано, оно не меняется в процессе запросов. Воспользуемся алгоритмом двоичного подъема.

Реализация алгоритма

Объявим рабочие массивы для алгоритма двоичного подъема.

#define MAX 100010

#define LOGMAX 18

vector<int> g[MAX];

int d[MAX], f[MAX];

int up[MAX][LOGMAX];

Поиск в глубину – построение массива up.

void dfs (int v, int p = 0, int len = 0)

{

int i, to;

d[v] = timer++;

up[v][0] = p;

for(i = 1; i <= l; i++)

up[v][i] = up[up[v][i-1]][i-1];

for(i = 0; i < g[v].size(); i++)

{

to = g[v][i];

if (to != p) dfs (to, v, len + 1);

}

f[v] = timer++;

}

Проверяем, является ли a отцом b.

int Parent(int a, int b)

{

return (d[a] <= d[b]) && (f[a] >= f[b]);

}

Вычисление наименьшего общего предка.

int LCA (int a, int b)

{

if (Parent(a, b)) return a;

if (Parent(b, a)) return b;

for (int i = l; i >= 0; i--)

if (!Parent(up[a][i], b)) a = up[a][i];

return up[a][0];

}

Основная часть программы. Читаем входные данные.

scanf("%d %d",&n,&m);

Найдем такое наименьшее l, для которого 2^l > n.

l = 1;

while ((1 << l) <= n) l++;

Читаем и строим дерево.

for(i = 1; i <= n - 1; i++)

{

scanf("%d",&v);

g[v].push_back(i);

g[i].push_back(v);

}

Запускаем поиск в глубину – алгоритм двоичного подъема.

timer = 0;

dfs(0);

Читаем данные для генерации запросов.

scanf("%d %d",&a1,&a2);

scanf("%lld %lld %lld",&x,&y,&z);

Генерируем запросы, выполняем их и вычисляем необходимую сумму.

v = sum = 0;

for(i = 0; i < m; i++)

{

v = LCA((a1 + v) % n, a2);

sum += v;

a1 = (x * a1 + y * a2 + z) % n;

a2 = (x * a2 + y * a1 + z) % n;

}

Выводим ответ.

printf("%lld\n",sum);