Спільний предок - 2#3299

Спільний предок - 2 (Розбір)

Задача вимагає реалізації запитів для знаходження найменшого спільного предка (НСП) пар вершин. Дерево задане і залишається незмінним протягом усіх запитів. Використаємо алгоритм бінарного підйому.

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

Оголосимо робочі масиви, що використовуються в алгоритмі бінарного підйому.

#define MAX 100010
#define LOGMAX 18
vector<int> g[MAX];
int d[MAX], f[MAX];
int up[MAX][LOGMAX];

Функція dfs виконує обхід дерева в глибину починаючи з вершини $v$ та будує таблицю предків $u p$ за допомогою методу бінарного підйому.

void dfs (int v, int p = 0, int len = 0) 
{
  d[v] = timer++;

  up[v][0] = p;
  for (int i = 1; i <= l; i++)
    up[v][i] = up[up[v][i-1]][i-1];

  for (int to : g[v])
    if (to != p) dfs (to, v, len + 1);

  f[v] = timer++;
}

C++

Функція Parent перевіряє, чи є вершина $a$ предком вершини $b$ .

int Parent(int a, int b)
{
  return (d[a] <= d[b]) && (f[a] >= f[b]);
}

Функція LCA обчислює найменшого спільного предка вершин $a$ та $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];
}

C++

Основна частина програми. Зчитуємо вхідні дані.

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

Знаходимо мінімальне значення $l$ таке, що $2^{l} > n$ 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;
}

C++

Виводимо відповідь.

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