Najniższy wspólny przodek (, LCA) – najniższym wspólnym przodkiem dwóch wierzchołków d oraz e w ukorzenionym drzewie T jest taki rodzic wierzchołków d oraz e, którego poziom w drzewie T jest największy.
Algorytm Zdefiniujmy tablicę p:
p[i, v] – wierzchołek u leżący na ścieżce pomiędzy v i korzeniem, taki że odległość (u, v) = 2i Jeśli taki wierzchołek nie istnieje, to p[i,v]=korzeń.
Rekurencyjnie można ją obliczyć ze wzoru
Za pomocą tak utworzonej tablicy możemy analogicznie do techniki wyszukiwania binarnego odnaleźć LCA dwóch wierzchołków.
Przykładowy kod w języku c++ obliczający LCA na podstawie tablicy p.
#include <cstdio> #include <vector>
#define MAX 1000005 #define LOGN 16
using namespace std;
vector<int> V[MAX]; int P[LOGN][MAX], pre[MAX], treeSize[MAX]; bool vis[MAX];
int n, from, to, counter=0;
bool children(int u, int v) { return (pre[u]>=pre[v] && pre[u] < pre[v]+treeSize[v]); }
int lca(int u, int v) { if(children(u, v)) return v; if(children(v, u))return u;
int i=u, j=LOGN-1; while(j>=0) { if(children(v, P[j][i])) j--; else i = P[j][i];
return P[i]; }
void dfs(int v) { counter++; pre[v]=counter; for(auto i:V[v]){ if(!vis[i]) { P[i]=v; vis[i]=true; dfs(i);
treeSize[v]=counter+1-pre[v]; }