Ümumi əcdad - 2 (Həll təhlili)

Məsələ, təpə cütləri üçün Ən Aşağı Ümumi Əcdad (LCA) tapılması sorğularının həyata keçirilməsini tələb edir. Ağac verilir və bütün sorğular ərzində dəyişməz qalır. Biz ikili qaldırma (binary lifting) alqoritmindən istifadə edəcəyik.

Alqoritmin həyata keçirilməsi

İkili qaldırma alqoritmində istifadə olunan iş massivlərini elan edin.

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

dfs funksiyası $v$ təpəsindən başlayaraq ağacın dərinlik üzrə keçidini həyata keçirir və ikili qaldırma metodu ilə $up$ əcdad cədvəlini qurur.

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++;
}

Parent funksiyası $a$ təpəsinin $b$ təpəsinin əcdadı olub-olmadığını yoxlayır.

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

LCA funksiyası $a$ və $b$ təpələrinin Ən Aşağı Ümumi Əcdadını hesablayır.

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];
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyun.

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

2^l > n şərtini ödəyən minimum $l$ dəyərini tapın.

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

Məlumatları oxuyun və ağacı qurun.

for (i = 1; i <= n - 1; i++)
{
  scanf("%d",&v);
  g[v].push_back(i);
  g[i].push_back(v);
}

İkili qaldırma alqoritmi üçün tələb olunan məlumat strukturunun qurulduğu dərinlik üzrə axtarışı işə salın.

timer = 0;
dfs(0);

Sorğuların generasiyası üçün lazım olan məlumatları oxuyun.

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

Sorğuları generasiya edin, onları ardıcıl olaraq emal edin və tələb olunan cəmi hesablayın.

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;
}

Cavabı çap edin.

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