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

Алгоритми 

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

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

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

Підрахунок offline 
Підрахунок offline полягає в тому, щоб порахувати функцію:  — вершина, у яку ми прийдемо, пройшовши уверх ребер з вершини , при чому, якщо ми прийшли в корінь дерева, то там і залишаємося. Для цього спочатку запустимо обхід в глибину з кореня і для кожної вершини запишемо номер її батька  та глибину вершини в підвішеному дереві . Якщо корінь — , то , тоді для функції  є рекурентна формула :

Для того, щоб відповідати на запити, нам потрібні тільки ті значення , для яких , бо для великих значень  дорівнюватиме значенню кореня.

Всього станів динаміки , де  кількість вершин у дереві. Кожний стан рахується за , тому загальна складність .

Відповіді на запити 
Відповідати на запити будемо за час . Спочатку помітимо, якщо вершина  для деяких  та  то . Тому, якщо , то пройдемо від вершини  на  кроків уверх, це і буде нове значення , яке ми можемо порахувати за . Число  ми можемо записати у двійковій системі числення як :

 і для всіх  пройти вверх послідовно із вершини  у вершину .

Далі вважаємо, що .

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

Інакше, якщо , то знайдемо такі вершини  та , що  та . Тоді відповіддю на запит буде .

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

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

Помітимо, що знайдені  строго спадають, оскільки, по-перше, щоразу ми знаходимо максимальне значення , а по-друге, два рази поспіль одне й те саме значення  отримати не можемо, бо  і ми тоді б взяли , тому можна перебирати всього  значень  в порядку спадання. Отже, складність відповіді .

Псевдокод 
  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]

Література 

 .
Наименьший общий предок. Нахождение за O (log N) (метод двоичного подъёма)
Метод двоичного подъема

Див. також 

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

Примітки 

Теорія графів
Алгоритми на графах
Найменший спільний предок вершин та в кореневому дереві — найвіддаленіша від кореня дерева вершина , яка лежить на обидвох шляхах від та до кореня дерева , тобто є предком обидвох вершин . Алгоритми Алгоритм двійкового підйому . ( Описано нижче в даній статті ) . Офлайновий алгоритм Тарджана Алгоритм Бендера — Фараха - Колтона . Опис алгоритму методу двійкового підйому Метод двійкового підйому — онлайн алгоритм вирішення задачі пошуку найменшого спільного предка . Він не використовує і заснований на методі динамічного програмування . Як і більшість online алгоритмів , цей метод спочатку робить підрахунок offline , а потім це використовує для відповіді на запити . Підрахунок offline Підрахунок offline полягає в тому , щоб порахувати функцію : — вершина , у яку ми прийдемо , пройшовши уверх ребер з вершини , при чому , якщо ми прийшли в корінь дерева , то там і залишаємося . Для цього спочатку запустимо обхід в глибину з кореня і для кожної вершини запишемо номер її батька та глибину вершини в підвішеному дереві \ . Якщо корінь — , то , тоді для функції є рекурентна формула \ : Для того , щоб відповідати на запити , нам потрібні тільки ті значення , для яких , бо для великих значень дорівнюватиме значенню кореня . Всього станів динаміки , де кількість вершин у дереві . Кожний стан рахується за , тому загальна складність \ . Відповіді на запити Відповідати на запити будемо за час \ . Спочатку помітимо , якщо вершина для деяких та то \ . Тому , якщо , то пройдемо від вершини на кроків уверх , це і буде нове значення , яке ми можемо порахувати за \. Число ми можемо записати у двійковій системі числення як \ : і для всіх пройти вверх послідовно із вершини у вершину \ . Далі вважаємо , що \ . Якщо , то відповідь на запит \ . Інакше , якщо , то знайдемо такі вершини та , що та \ . Тоді відповіддю на запит буде \ . Щоб знайти вершини та , спочатку ініціалізуємо та , та знаходитимемо таке максимальне , що \ . Тоді піднімемося вгору на кроків угору з обидвох вершин , та повторимо цю процедуру . Якщо такого знайти не можна , то знайдені вершини і є тими , які нам потрібно знайти , бо \ . Оцінимо час роботи алгоритму . Помітимо , що знайдені строго спадають , оскільки , по-перше , щоразу ми знаходимо максимальне значення , а по-друге , два рази поспіль одне й те саме значення отримати не можемо , бо і ми тоді б взяли , тому можна перебирати всього значень в порядку спадання . Отже , складність відповіді \ . Псевдокод function preprocess ( ) : int [ ] p = dfs ( 0 ) for i =to n dp [ i ] [ 0 ] = p[i ] for j =to log ( n ) for i =to n dp [ i ] [ j ] = dp[dp [ i ] [ j - ] [ j - 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 ] Література \ . Наименьший общий предок . Нахождение за O ( log N ) ( метод двоичного подъёма ) Метод двоичного подъема Див . також Теорія графів Дерево ( теорія графів ) Примітки Теорія графів Алгоритми на графах