L'ancêtre commun le plus proche (LCA) de deux nœuds u et v dans un arbre enraciné est le nœud le plus profond qui est un ancêtre à la fois de u et de v. Par exemple, dans l'arbre ci-dessous, LCA(3,7) = 1 et LCA(3,4) = 2.
Il existe plusieurs méthodes pour calculer le LCA, classifiées en algorithmes hors ligne (toutes les requêtes sont connues à l'avance) et en ligne (les requêtes sont traitées au fur et à mesure). Voici les quatre approches principales.
Algorithmes hors ligne
Les requêtes sont connues avant le traitement, et leur ordre n'a pas d'importance.
1. Algorithme de Tarjan
L'algorithme lit d'abord toutes les paires de requêtes, puis effectue un seul parcours en profondeur (DFS). Pendant le DFS, pour chaque nœud visité, on explore d'abord ses enfants. Après avoir exploré un enfant, on fusionne (via une structure Union-Find) l'enfant avec le nœud courant. Lorsqu'on rencontre une paire de requêtes dont un des nœuds a déjà été visité, on peut déterminer le LCA grâce à la fonction de recherche de l'Union-Find sur le nœud déjà visité.
Ce processus peut être visualisé comme une montée d'eau depuis une feuille : l'eau remonte jusqu'à un embranchement, puis se répand dans les branches frères. Le LCA est le point le plus haut où l'eau a inondé les deux nœuds de la requête.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
struct Edge { int v, next; } edges[MAXN << 1];
int head[MAXN], ecount;
void addEdge(int u, int v) {
edges[ecount] = {v, head[u]};
head[u] = ecount++;
}
struct Query {
int v, id, next;
} queries[MAXN << 1];
int qhead[MAXN], qcount;
void addQuery(int u, int v, int id) {
queries[qcount] = {v, id, qhead[u]};
qhead[u] = qcount++;
}
int parent[MAXN];
int findSet(int x) { return parent[x] == x ? x : parent[x] = findSet(parent[x]); }
int visited[MAXN];
int answers[MAXN];
void tarjanDFS(int u) {
visited[u] = 1;
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].v;
if (!visited[v]) {
tarjanDFS(v);
parent[v] = u;
}
}
for (int i = qhead[u]; i != -1; i = queries[i].next) {
int v = queries[i].v;
if (visited[v])
answers[queries[i].id] = findSet(v);
}
}
int main() {
memset(head, -1, sizeof(head));
memset(qhead, -1, sizeof(qhead));
int n, m, root;
scanf("%d %d %d", &n, &m, &root);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
addQuery(u, v, i);
addQuery(v, u, i);
}
for (int i = 1; i <= n; i++) parent[i] = i;
tarjanDFS(root);
for (int i = 1; i <= m; i++)
printf("%d\n", answers[i]);
return 0;
}
Algorithmes en ligne
Les requêtes sont inconnues ou doivent être traitées dans un ordre précis.
1. Méthode des sauts binaires (Binary Lifting)
L'idée est de précalculer pour chaque nœud ses ancêtres à des distances de puissance de 2 (2i), ainsi que la profondeur de chaque nœud. Pour répondre à une requête (u, v) :
- On ramène le nœud le plus profond (par exemple u) à la même profondeur que l'autre en utilisant la représentation binaire de la différence de profondeur.
- On remonte ensuite simultanément les deux nœuds en sautant des paliers de 2i tant que leurs ancêtres diffèrent.
- À la fin, soit u = v (cas racine), soit le LCA est le parent direct de u (ou v).
La complexité est O(n log n) en préparation et O(log n) par requête. Dans les cas pratiques, la profondeur de l'arbre influence le temps : pour un arbre chaîne, log profondeur = log n.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
const int LOG = 20;
struct Edge { int v, next; } edges[MAXN << 1];
int head[MAXN], ecount;
void addEdge(int u, int v) {
edges[ecount] = {v, head[u]};
head[u] = ecount++;
}
int up[MAXN][LOG];
int depth[MAXN];
void dfs(int u, int parent) {
up[u][0] = parent;
depth[u] = depth[parent] + 1;
for (int j = 1; j < LOG; j++)
up[u][j] = up[up[u][j-1]][j-1];
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].v;
if (v != parent)
dfs(v, u);
}
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int j = 0; diff; j++, diff >>= 1)
if (diff & 1) u = up[u][j];
if (u == v) return u;
for (int j = LOG-1; j >= 0; j--)
if (up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
return up[u][0];
}
int main() {
memset(head, -1, sizeof(head));
int n, m, root;
scanf("%d %d %d", &n, &m, &root);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
dfs(root, root);
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
printf("%d\n", lca(u, v));
}
return 0;
}
2. Séquence d'Euler + RMQ
On construit une séquence d'Euler de l'arbre : à chaque fois qu'on visite un nœud (en entrant, et après chaque retour d'un fils), on l'ajoute à une liste. La longueur de cette liste est 2×n - 1. On enregistre aussi la première position de chaque nœud dans cette séquence (pos[u]) et la profondeur associée à chaque élément de la séquence.
Le LCA de deux nœuds u et v est alors le nœud de profondeur minimale dans le segment de la séquence d'Euler entre pos[u] et pos[v] (avec pos[u] < pos[v]). Ce minimum de plage (RMQ) peut être calculé avec une table de sauts (Sparse Table) pour une réponse en O(1).
La préparation est O(n log n) dans tous les cas (optimal comme pire), mais la requête est constante.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
const int LOG = 20;
struct Edge { int v, next; } edges[MAXN << 1];
int head[MAXN], ecount;
void addEdge(int u, int v) {
edges[ecount] = {v, head[u]};
head[u] = ecount++;
}
int euler[2*MAXN], depth[2*MAXN], first[MAXN], eulerLen;
int st[2*MAXN][LOG];
void dfs(int u, int parent, int d) {
first[u] = eulerLen;
euler[eulerLen] = u;
depth[eulerLen] = d;
eulerLen++;
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].v;
if (v != parent) {
dfs(v, u, d+1);
euler[eulerLen] = u;
depth[eulerLen] = d;
eulerLen++;
}
}
}
void buildRMQ() {
for (int i = 0; i < eulerLen; i++) st[i][0] = i;
for (int j = 1; (1 << j) <= eulerLen; j++)
for (int i = 0; i + (1 << j) - 1 < eulerLen; i++)
st[i][j] = (depth[st[i][j-1]] < depth[st[i+(1<<(j-1))][j-1]]) ?
st[i][j-1] : st[i+(1<<(j-1))][j-1];
}
int queryRMQ(int l, int r) {
int k = log2(r - l + 1);
int left = st[l][k];
int right = st[r-(1<<k)+1][k];
return (depth[left] < depth[right]) ? euler[left] : euler[right];
}
int lca(int u, int v) {
int l = first[u], r = first[v];
if (l > r) swap(l, r);
return queryRMQ(l, r);
}
int main() {
memset(head, -1, sizeof(head));
int n, m, root;
scanf("%d %d %d", &n, &m, &root);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
dfs(root, root, 0);
buildRMQ();
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
printf("%d\n", lca(u, v));
}
return 0;
}
3. Décomposition en chaînes lourdes (Heavy-Light Decomposition - HLD)
On décompose l'arbre en chaînes lourdes (heavy paths) lors de deux DFS : le premier calcule la taille des sous-arbres et identifie les fils lourds ; le second assigne chaque nœud à une chaîne. Pour répondre à une requête LCA(u, v), on remonte le long des chaînes jusqu'à ce que les deux nœuds soient sur la même chaîne. Le LCA est alors le nœud de profondeur minimale parmi les deux.
La préparation est O(n) et chaque requête est O(log n). Cette technique supporte des mises à jour dynamiques (avec Link-Cut Tree par exemple).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
struct Edge { int v, next; } edges[MAXN << 1];
int head[MAXN], ecount;
void addEdge(int u, int v) {
edges[ecount] = {v, head[u]};
head[u] = ecount++;
}
int parent[MAXN], depth[MAXN], subtreeSize[MAXN];
int heavyChild[MAXN];
void dfs1(int u, int p) {
parent[u] = p;
depth[u] = depth[p] + 1;
subtreeSize[u] = 1;
heavyChild[u] = -1;
int maxSize = 0;
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].v;
if (v != p) {
dfs1(v, u);
subtreeSize[u] += subtreeSize[v];
if (subtreeSize[v] > maxSize) {
maxSize = subtreeSize[v];
heavyChild[u] = v;
}
}
}
}
int headChain[MAXN], position[MAXN], curPos;
void dfs2(int u, int h) {
headChain[u] = h;
position[u] = curPos++;
if (heavyChild[u] != -1)
dfs2(heavyChild[u], h);
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].v;
if (v != parent[u] && v != heavyChild[u])
dfs2(v, v);
}
}
int lca(int u, int v) {
while (headChain[u] != headChain[v]) {
if (depth[headChain[u]] < depth[headChain[v]])
swap(u, v);
u = parent[headChain[u]];
}
return depth[u] < depth[v] ? u : v;
}
int main() {
memset(head, -1, sizeof(head));
int n, m, root;
scanf("%d %d %d", &n, &m, &root);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
depth[root] = 0;
dfs1(root, root);
dfs2(root, root);
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
printf("%d\n", lca(u, v));
}
return 0;
}