L'algorithme du plus proche ancêtre commun (LCA) dans un arbre repose sur des techniques de prétraitement pour optimiser les requêtes. Trois types de relations d'ascendance existent entre deux nœuds : a est ancêtre de b, b est ancêtre de a, ou aucun lien direct.

Pour un ensemble de nœuds, le LCA peut être déterminé en identifient les points avec les ordres de parcours en profondeur (DFS) minimum et maximum. La connaissance de la racine est essentielle pour le prétraitement.

La méthode de saut par puissance de deux (倍增法) offre une complexité de prétraitement en O(n log n) et de requête en O(log n). Elle utilise un tableau où f[i][j] représente l'ancêtre à 2^j générations au-dessus du nœud i.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 40010, MAX_M = 2 * MAX_N;

int n, m;
int adj[MAX_N], e[MAX_M], nxt[MAX_M], idx;
int prof[MAX_N], anc[MAX_N][16];
int queue[MAX_N];

void ajouter(int u, int v) {
    e[idx] = v;
    nxt[idx] = adj[u];
    adj[u] = idx++;
}

void bfs(int racine) {
    memset(prof, 0x3f, sizeof prof);
    prof[0] = 0;
    prof[racine] = 1;
    int debut = 0, fin = 0;
    queue[0] = racine;
    while (debut <= fin) {
        int courant = queue[debut++];
        for (int i = adj[courant]; i != -1; i = nxt[i]) {
            int voisin = e[i];
            if (prof[voisin] > prof[courant] + 1) {
                prof[voisin] = prof[courant] + 1;
                queue[++fin] = voisin;
                anc[voisin][0] = courant;
                for (int k = 1; k <= 15; k++) {
                    anc[voisin][k] = anc[anc[voisin][k-1]][k-1];
                }
            }
        }
    }
}

int lca(int a, int b) {
    if (prof[a] < prof[b]) swap(a, b);
    for (int k = 15; k >= 0; k--) {
        if (prof[anc[a][k]] >= prof[b])
            a = anc[a][k];
    }
    if (a == b) return a;
    for (int k = 15; k >= 0; k--) {
        if (anc[a][k] != anc[b][k]) {
            a = anc[a][k];
            b = anc[b][k];
        }
    }
    return anc[a][0];
}

int main() {
    cin >> n;
    int racine = 0;
    memset(adj, -1, sizeof adj);
    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        if (v == -1) racine = u;
        else ajouter(u, v), ajouter(v, u);
    }

    bfs(racine);
    cin >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        int p = lca(a, b);
        if (p == a) cout << 1 << endl;
        else if (p == b) cout << 2 << endl;
        else cout << 0 << endl;
    }
    return 0;
}

L'algorithme de Tarjan permet de calculer les LCA hors ligne en O(n + m) en utliisant une recherche récursive et une structure d'ensemble disjoint. Les nœuds sont classés en trois catégories : déjà visités et en retour, en cours de recherche, ou non visités.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_N = 20010, MAX_M = 2 * MAX_N;

int n, m;
int adj[MAX_N], e[MAX_M], nxt[MAX_M], poids[MAX_M], idx;
int parent[MAX_N];
int dist[MAX_N];
vector<pair<int, int>> requetes[MAX_N];
int etat[MAX_N];
int resultats[MAX_N];

void ajouter(int u, int v, int p) {
    e[idx] = v;
    poids[idx] = p;
    nxt[idx] = adj[u];
    adj[u] = idx++;
}

void calculerDistances(int u, int pere) {
    for (int i = adj[u]; i != -1; i = nxt[i]) {
        int v = e[i];
        if (v == pere) continue;
        dist[v] = dist[u] + poids[i];
        calculerDistances(v, u);
    }
}

int trouver(int x) {
    if (parent[x] != x) parent[x] = trouver(parent[x]);
    return parent[x];
}

void tarjan(int u) {
    etat[u] = 1;
    for (int i = adj[u]; i != -1; i = nxt[i]) {
        int v = e[i];
        if (!etat[v]) {
            tarjan(v);
            parent[v] = u;
        }
    }
    for (auto& req : requetes[u]) {
        int v = req.first, id = req.second;
        if (etat[v] == 2) {
            int anc = trouver(v);
            resultats[id] = dist[u] + dist[v] - 2 * dist[anc];
        }
    }
    etat[u] = 2;
}

int main() {
    cin >> n >> m;
    memset(adj, -1, sizeof adj);
    for (int i = 0; i < n - 1; i++) {
        int u, v, p;
        cin >> u >> v >> p;
        ajouter(u, v, p);
        ajouter(v, u, p);
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        if (a != b) {
            requetes[a].push_back({b, i});
            requetes[b].push_back({a, i});
        }
    }
    for (int i = 1; i <= n; i++) parent[i] = i;

    calculerDistances(1, -1);
    tarjan(1);

    for (int i = 0; i < m; i++) {
        cout << resultats[i] << endl;
    }
    return 0;
}

Dans des problèmes impliquant la suppression de points d'un ensemble, comme comparer des arbres, le LCA d'un ensemble peut être obtenu en appliquant l'algorithme aux points avec les ordres DFS extrêmes. La distance entre deux nœuds est donnée par d[x] + d[y] - 2*d[p].

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 100010, LOG = 31;

int profondeurA[MAX_N], ancA[MAX_N][LOG], profondeurB[MAX_N], ancB[MAX_N][LOG];
int ordreDfsA[MAX_N], ordreDfsB[MAX_N], valeurA[MAX_N], valeurB[MAX_N];
vector<int> arbreA[MAX_N], arbreB[MAX_N];

bool comparerA(int x, int y) {
    return ordreDfsA[x] < ordreDfsA[y];
}

bool comparerB(int x, int y) {
    return ordreDfsB[x] < ordreDfsB[y];
}

void dfsA(int u, int pere, int& compteur) {
    ancA[u][0] = pere;
    ordreDfsA[u] = compteur++;
    profondeurA[u] = profondeurA[pere] + 1;
    for (int i = 1; i < LOG; i++) {
        ancA[u][i] = ancA[ancA[u][i-1]][i-1];
    }
    for (int v : arbreA[u]) {
        if (v == pere) continue;
        dfsA(v, u, compteur);
    }
}

void dfsB(int u, int pere, int& compteur) {
    ancB[u][0] = pere;
    ordreDfsB[u] = compteur++;
    profondeurB[u] = profondeurB[pere] + 1;
    for (int i = 1; i < LOG; i++) {
        ancB[u][i] = ancB[ancB[u][i-1]][i-1];
    }
    for (int v : arbreB[u]) {
        if (v == pere) continue;
        dfsB(v, u, compteur);
    }
}

int lcaA(int x, int y) {
    if (profondeurA[x] > profondeurA[y]) swap(x, y);
    int diff = profondeurA[y] - profondeurA[x];
    for (int i = 0; diff; i++, diff >>= 1) {
        if (diff & 1) y = ancA[y][i];
    }
    if (x == y) return x;
    for (int i = LOG-1; i >= 0; i--) {
        if (ancA[x][i] != ancA[y][i]) {
            x = ancA[x][i];
            y = ancA[y][i];
        }
    }
    return ancA[x][0];
}

int lcaB(int x, int y) {
    if (profondeurB[x] > profondeurB[y]) swap(x, y);
    int diff = profondeurB[y] - profondeurB[x];
    for (int i = 0; diff; i++, diff >>= 1) {
        if (diff & 1) y = ancB[y][i];
    }
    if (x == y) return x;
    for (int i = LOG-1; i >= 0; i--) {
        if (ancB[x][i] != ancB[y][i]) {
            x = ancB[x][i];
            y = ancB[y][i];
        }
    }
    return ancB[x][0];
}

void resoudre() {
    int n, m, x;
    cin >> n >> m;
    vector<int> ensembleA(m), ensembleB(m);
    for (int i = 0; i < m; i++) {
        cin >> ensembleA[i];
        ensembleB[i] = ensembleA[i];
    }
    for (int i = 1; i <= n; i++) cin >> valeurA[i];
    for (int i = 2; i <= n; i++) {
        cin >> x;
        arbreA[x].push_back(i);
    }
    int compteur = 1;
    dfsA(1, 0, compteur);
    for (int i = 1; i <= n; i++) cin >> valeurB[i];
    for (int i = 2; i <= n; i++) {
        cin >> x;
        arbreB[x].push_back(i);
    }
    compteur = 1;
    dfsB(1, 0, compteur);

    sort(ensembleA.begin(), ensembleA.end(), comparerA);
    sort(ensembleB.begin(), ensembleB.end(), comparerB);
    int compte = 0;
    for (int i = 0; i < m; i++) {
        int xA = ensembleA[0], yA = ensembleA[m-1];
        int xB = ensembleB[0], yB = ensembleB[m-1];
        if (i == 0) xA = ensembleA[1];
        else if (i == m-1) yA = ensembleA[m-2];
        if (xB == ensembleA[i]) xB = ensembleB[1];
        else if (yB == ensembleA[i]) yB = ensembleB[m-2];

        int lca_x = lcaA(xA, yA);
        int lca_y = lcaB(xB, yB);
        if (valeurA[lca_x] > valeurB[lca_y]) compte++;
    }
    cout << compte << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--) resoudre();
    return 0;
}