Найменший спільний предок

Найменший спільний предок вершин $u$ та $v$ в кореневому дереві $T$ — найвіддаленіша від кореня дерева вершина, яка лежить на обидвох шляхах від $u$ та $v$ до кореня дерева, тобто є предком обидвох вершин.

Алгоритми

• Алгоритм двійкового підйому. (Описано нижче в даній статті).
• Офлайновий алгоритм Тарджана
• Алгоритм Бендера — Фараха-Колтона.

Опис алгоритму методу двійкового підйому

Метод двійкового підйому — онлайн алгоритм вирішення задачі пошуку найменшого спільного предка. Він не використовує діапазон мінімального запиту і заснований на методі динамічного програмування.

Як і більшість online алгоритмів, цей метод спочатку робить підрахунок offline, а потім це використовує для відповіді на запити.

Підрахунок offline

Підрахунок offline полягає в тому, щоб порахувати функцію: $dp[v][i]$ — вершина, у яку ми прийдемо, пройшовши уверх $2^{i}$ребер з вершини $v$, при чому, якщо ми прийшли в корінь дерева, то там і залишаємося. Для цього спочатку запустимо обхід в глибину з кореня і для кожної вершини запишемо номер її батька $p[v]$ та глибину вершини в підвішеному дереві $d[v]$. Якщо корінь — $v$, то $p[v]=v$, тоді для функції $dp$ є рекурентна формула :

$dp[v][i]={\begin{cases}p[v],&i=0,\\dp[dp[v][i-1]][i-1],&i>0.\end{cases}}$

Для того, щоб відповідати на запити, нам потрібні тільки ті значення $dp[v][i]$, для яких $i\leqslant \log _{2}n$, бо для великих значень $i\ \ dp[v][i]$ дорівнюватиме значенню кореня.

Всього станів динаміки $O(n\log n)$, де $n$ кількість вершин у дереві. Кожний стан рахується за $O(1)$, тому загальна складність $O(n\log n)$.

Відповіді на запити

Відповідати на запити будемо за час $O(\log n)$. Спочатку помітимо, якщо вершина $c=LCA(u,v)$ для деяких $u$ та $v$ то $d[c]\leq \min(d[u],d[v])$. Тому, якщо $d[u]>d[v]$, то пройдемо від вершини $u$ на $(d[u]-d[v])$ кроків уверх, це і буде нове значення $u$, яке ми можемо порахувати за $O(\log n)$. Число $(d[u]-d[v])$ ми можемо записати у двійковій системі числення як :

$2^{i_{1}}+2^{i_{2}}+...2^{i_{l}}$ і для всіх $i_{j}$ пройти вверх послідовно із вершини $u$ у вершину $dp[u][i_{j}]$.

Далі вважаємо, що $d[v]=d[u]$.

Якщо $v=u$, то відповідь на запит $v$.

Інакше, якщо $v\neq u$, то знайдемо такі вершини $x$ та $y$, що $x\neq y$ та $p[x]=p[y]$. Тоді відповіддю на запит буде $p[x]$.

Щоб знайти вершини $x$ та $y$, спочатку ініціалізуємо $x=v$ та $y=u$, та знаходитимемо таке максимальне $k$, що $dp[x][k]\neq dp[y][k]$. Тоді піднімемося вгору на $2^{k}$ кроків угору з обидвох вершин, та повторимо цю процедуру. Якщо такого $k$ знайти не можна, то знайдені вершини і є тими, які нам потрібно знайти, бо $p[x]=dp[x][0]=dp[y][0]=p[y]$.

Оцінимо час роботи алгоритму.

Помітимо, що знайдені $k$ строго спадають, оскільки, по-перше, щоразу ми знаходимо максимальне значення $k$, а по-друге, два рази поспіль одне й те саме значення $k$ отримати не можемо, бо $2^{k}+2^{k}=2^{k+1}$ і ми тоді б взяли $k+1$, тому можна перебирати всього $O(\log n)$ значень $k$ в порядку спадання. Отже, складність відповіді $O(\log n)$.

Псевдокод

  function preprocess():
     int[] p = dfs(0)
     for i = 1 to n
        dp[i][0] = p[i]
     for j = 1 to log(n)
        for i = 1 to n
           dp[i][j] = dp[dp[i][j - 1]][j - 1]
  
  int lca(int v, int u):
     if d[v] > d[u]
        swap(v, u)
     for i = log(n) downto 0
        if d[u] - d[v] 
           u = dp[u][i]
     if v == u
        return v
     for i = log(n) downto 0
        if dp[v][i] != dp[u][i]
           v = dp[v][i]
           u = dp[u][i]
     return p[v]

Література

• Aho, Alfred; Hopcroft, John; Ullman, Jeffrey (1973), On finding lowest common ancestors in trees, Proc. 5th ACM Symp. Theory of Computing (STOC), с. 253—265, doi:10.1145/800125.804056.
• Наименьший общий предок. Нахождение за O (log N) (метод двоичного подъёма)
• Метод двоичного подъема

Див. також

• Теорія графів
• Дерево (теорія графів)