L'algorithme du plus ancêtre commun (LCA) est une technique fondamentale pour résoudre des problèmes de distance ou de relations dans des arbres. Cet article présente plusieurs problèmes d'entraînement pour maîtriser le LCA, avec des explications et des implémentations en C++.

Problème 1 : Distance entre maisons

Lien : HDU 2586

Description : Un village a n maisons connectées par des routes bidirectionnelles. Entre deux maisons, il existe toujours un chemin unique. Pour chaque requête, calculre la distance entre deux maisons spécifiées.

Entrée : D'abord le nombre de cas de test T (T <= 10). Pour chaque cas, deux entiers n et m (n maisons, m requêtes), suivis de n-1 lignes décrivant les routes (u, v, longueur), puis m requêtes.

Sortie : Pour chaque requête, la distance. Une ligne vide après chaque cas de test.

Approche : C'est un problème direct de LCA pour calculer la distance dans un arbre. La distance entre u et v est donnée par cost[u] + cost[v] - 2 * cost[lca(u, v)], où cost[x] est la distance depuis la racine.

Implémentation (C++) :

#include <cstdio>
#include <vector>
using namespace std;

const int max_vertices = 40000 + 7;
int num_nodes, num_queries, node1, node2, weight;
int ancestor[max_vertices][30], depth[max_vertices], dist_from_root[max_vertices];

struct Arc {
    int target, length;
    Arc(int t = 0, int l = 0) : target(t), length(l) {}
};

vector<Arc> graph[max_vertices];

void depth_first_search(int current, int current_depth, int parent) {
    depth[current] = current_depth;
    ancestor[current][0] = parent;
    for (const auto& arc : graph[current]) {
        int neighbor = arc.target;
        if (neighbor != parent) {
            dist_from_root[neighbor] = dist_from_root[current] + arc.length;
            depth_first_search(neighbor, current_depth + 1, current);
        }
    }
}

void preprocess_lca() {
    for (int i = 1; i <= num_nodes; ++i) {
        for (int j = 1; (1 << j) <= num_nodes; ++j) {
            ancestor[i][j] = -1;
        }
    }
    for (int j = 1; (1 << j) <= num_nodes; ++j) {
        for (int i = 1; i <= num_nodes; ++i) {
            if (ancestor[i][j - 1] != -1) {
                ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1];
            }
        }
    }
}

int find_lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int max_shift;
    for (max_shift = 0; (1 << (max_shift + 1)) <= depth[u]; ++max_shift);
    for (int i = max_shift; i >= 0; --i) {
        if (depth[u] - (1 << i) >= depth[v]) {
            u = ancestor[u][i];
        }
    }
    if (u == v) return u;
    for (int i = max_shift; i >= 0; --i) {
        if (ancestor[u][i] != -1 && ancestor[u][i] != ancestor[v][i]) {
            u = ancestor[u][i];
            v = ancestor[v][i];
        }
    }
    return ancestor[u][0];
}

int main() {
    int test_cases;
    scanf("%d", &test_cases);
    while (test_cases--) {
        scanf("%d%d", &num_nodes, &num_queries);
        for (int i = 1; i <= num_nodes; ++i) graph[i].clear();
        for (int i = 1; i < num_nodes; ++i) {
            scanf("%d%d%d", &node1, &node2, &weight);
            graph[node1].push_back(Arc(node2, weight));
            graph[node2].push_back(Arc(node1, weight));
        }
        depth_first_search(1, 0, -1);
        preprocess_lca();
        while (num_queries--) {
            scanf("%d%d", &node1, &node2);
            int lca = find_lca(node1, node2);
            printf("%d\n", dist_from_root[node1] + dist_from_root[node2] - 2 * dist_from_root[lca]);
        }
    }
    return 0;
}

Problème 2 : Connexions entre villes

Lien : HDU 2874

Description : Après une guerre, des villes peuvent être déconnectées. Donné un graphe acyclique, pour chaque requête, déterminer si deux villes sont connectées et, si oui, calculer la plus courte distance.

Entrée : Cas multiples. Chaque cas commence avec n, m, c (n villes, m routes, c requêtes). Suivi de m lignes de routes et c requêtes.

Sortie : Pour chaque requête, "Not connected" si pas de chemin, sinon la distance.

Approche : Utiliser LCA sur chaque composante connexe. Si deux nœuds n'ont pas le même ancêtre commun depuis la racine, ils ne sont pas connectés.

Implémentation (C++) :

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int max_cities = 10000 + 7;
int n, m, q, a, b, len;
int ancestor[max_cities][30], depth[max_cities], dist_root[max_cities];

struct Edge {
    int to, cost;
    Edge(int t = 0, int c = 0) : to(t), cost(c) {}
};

vector<Edge> adj[max_cities];

void dfs(int node, int dep, int parent) {
    depth[node] = dep;
    ancestor[node][0] = parent;
    for (const auto& e : adj[node]) {
        int next = e.to;
        if (next != parent) {
            dist_root[next] = dist_root[node] + e.cost;
            dfs(next, dep + 1, node);
        }
    }
}

void build_lca() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; (1 << j) <= n; ++j) ancestor[i][j] = -1;
    }
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i <= n; ++i) {
            if (ancestor[i][j - 1] != -1)
                ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1];
        }
    }
}

int lca_query(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int step;
    for (step = 0; (1 << (step + 1)) <= depth[u]; ++step);
    for (int i = step; i >= 0; --i) {
        if (depth[u] - (1 << i) >= depth[v]) u = ancestor[u][i];
    }
    if (u == v) return u;
    for (int i = step; i >= 0; --i) {
        if (ancestor[u][i] != -1 && ancestor[u][i] != ancestor[v][i]) {
            u = ancestor[u][i];
            v = ancestor[v][i];
        }
    }
    return ancestor[u][0];
}

int main() {
    while (scanf("%d%d%d", &n, &m, &q) != EOF) {
        memset(dist_root, 0, sizeof(dist_root));
        for (int i = 0; i <= n; ++i) adj[i].clear();
        for (int i = 0; i < m; ++i) {
            scanf("%d%d%d", &a, &b, &len);
            adj[a].push_back(Edge(b, len));
            adj[b].push_back(Edge(a, len));
        }
        for (int i = 1; i <= n; ++i) {
            if (depth[i] == 0) {
                dfs(i, 0, -1);
            }
        }
        build_lca();
        while (q--) {
            scanf("%d%d", &a, &b);
            int lca = lca_query(a, b);
            if (lca == -1 || (dist_root[a] == 0 && dist_root[b] == 0 && lca == -1)) {
                printf("Not connected\n");
            } else {
                printf("%d\n", dist_root[a] + dist_root[b] - 2 * dist_root[lca]);
            }
        }
    }
    return 0;
}

Problème 3 : Requêtes de distance

Lien : POJ 1986

Description : Fermier John veut trouver des distances dans une grille de fermes. Donné un arbre avec des directions, calculer la distance entre deux nœuds pour plusieurs requêtes.

Entrée : Similaire aux problèmes précédents, avec des directions ignorées.

Sortie : La distance pour chaque requête.

Approche : Directement appliquer LCA, en ignorant les directions dans l'entrée.

Implémentation (C++) :

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int max_farms = 100000 + 7;
int num_farms, num_roads, queries, farm1, farm2, road_len;
int anc[max_farms][30], d[max_farms], cost[max_farms];

struct Connection {
    int dest, distance;
    Connection(int d = 0, int l = 0) : dest(d), distance(l) {}
};

vector<Connection> farm_graph[max_farms];

void traverse(int node, int depth_val, int parent) {
    d[node] = depth_val;
    anc[node][0] = parent;
    for (const auto& conn : farm_graph[node]) {
        int next = conn.dest;
        if (next != parent) {
            cost[next] = cost[node] + conn.distance;
            traverse(next, depth_val + 1, node);
        }
    }
}

void prepare_lca() {
    for (int i = 1; i <= num_farms; ++i) {
        for (int j = 1; (1 << j) <= num_farms; ++j) anc[i][j] = -1;
    }
    for (int j = 1; (1 << j) <= num_farms; ++j) {
        for (int i = 1; i <= num_farms; ++i) {
            if (anc[i][j - 1] != -1)
                anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}

int find_common_ancestor(int u, int v) {
    if (d[u] < d[v]) swap(u, v);
    int shift;
    for (shift = 0; (1 << (shift + 1)) <= d[u]; ++shift);
    for (int i = shift; i >= 0; --i) {
        if (d[u] - (1 << i) >= d[v]) u = anc[u][i];
    }
    if (u == v) return u;
    for (int i = shift; i >= 0; --i) {
        if (anc[u][i] != -1 && anc[u][i] != anc[v][i]) {
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    return anc[u][0];
}

int main() {
    while (scanf("%d%d", &num_farms, &num_roads) != EOF) {
        memset(cost, 0, sizeof(cost));
        for (int i = 0; i <= num_farms; ++i) farm_graph[i].clear();
        for (int i = 0; i < num_roads; ++i) {
            scanf("%d%d%d%*s", &farm1, &farm2, &road_len);
            farm_graph[farm1].push_back(Connection(farm2, road_len));
            farm_graph[farm2].push_back(Connection(farm1, road_len));
        }
        traverse(1, 0, -1);
        prepare_lca();
        scanf("%d", &queries);
        while (queries--) {
            scanf("%d%d", &farm1, &farm2);
            int lca = find_common_ancestor(farm1, farm2);
            printf("%d\n", cost[farm1] + cost[farm2] - 2 * cost[lca]);
        }
    }
    return 0;
}

Problème 4 : Plus ancêtre commun le plus proche

Lien : POJ 1330

Description : Trouver le plus ancêtre commmun le plus proche dans un arbre enraciné avec des relations parent-enfant données.

Entrée : T cas de test. Chaque cas a n nœuds, n-1 arêtes (parent enfant), et une requête.

Sortie : Le nœud LCA.

Approche : Déterminer la racine par le degré entrant, puis appliquer LCA.

Implémentaiton (C++) :

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int max_nodes = 10000 + 7;
int cases, n, x, y, root;
int d[max_nodes], anc[max_nodes][30], in_degree[max_nodes];

vector<int> tree[max_nodes];

void dfs(int u, int depth_val, int p) {
    d[u] = depth_val;
    anc[u][0] = p;
    for (int v : tree[u]) {
        if (v != p) {
            dfs(v, depth_val + 1, u);
        }
    }
}

void build_ancestors() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; (1 << j) <= n; ++j) anc[i][j] = -1;
    }
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i <= n; ++i) {
            if (anc[i][j - 1] != -1)
                anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}

int lca(int u, int v) {
    if (d[u] < d[v]) swap(u, v);
    int step;
    for (step = 0; (1 << (step + 1)) <= d[u]; ++step);
    for (int i = step; i >= 0; --i) {
        if (d[u] - (1 << i) >= d[v]) u = anc[u][i];
    }
    if (u == v) return u;
    for (int i = step; i >= 0; --i) {
        if (anc[u][i] != -1 && anc[u][i] != anc[v][i]) {
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    return anc[u][0];
}

int main() {
    scanf("%d", &cases);
    while (cases--) {
        scanf("%d", &n);
        for (int i = 0; i <= n; ++i) tree[i].clear();
        memset(in_degree, 0, sizeof(in_degree));
        for (int i = 1; i < n; ++i) {
            scanf("%d%d", &x, &y);
            tree[x].push_back(y);
            tree[y].push_back(x);
            in_degree[y]++;
        }
        for (int i = 1; i <= n; ++i) {
            if (in_degree[i] == 0) {
                root = i;
                break;
            }
        }
        dfs(root, 0, -1);
        build_ancestors();
        scanf("%d%d", &x, &y);
        printf("%d\n", lca(x, y));
    }
    return 0;
}

Problème 5 : Opérations CD

Lien : HDU 4547

Description : Minimiser le nombre d'opérations CD pour naviguer entre répertoires dans un système de fichiers arborescent. CD avec un chemin ou CD .. pour remonter.

Entrée : T cas. Chaque cas a n répertoires et m requêtes, avec des relations parent-enfant sous forme de chaînes.

Sortie : Le nombre minimal d'opérations CD pour chaque requête.

Approche : Mapper les noms à des identifiants numériques, trouver la racine, puis utiliser LCA. Si la destination est un ancêtre, le coût est la différence de profondeur, sinon ajouter 1.

Implémentation (C++) :

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

const int max_dirs = 100000 + 7;
int t, n, m, cnt;
string name1, name2;
int dist[max_dirs], depth[max_dirs], anc[max_dirs][30], in_deg[max_dirs];

struct DirEdge {
    int to, steps;
    DirEdge(int t = 0, int s = 0) : to(t), steps(s) {}
};

vector<DirEdge> dir_graph[max_dirs];
map<string, int> id_map;

void init() {
    cnt = 0;
    id_map.clear();
    memset(in_deg, 0, sizeof(in_deg));
    memset(dist, 0, sizeof(dist));
    for (int i = 0; i <= n; ++i) dir_graph[i].clear();
}

void dfs(int u, int d_val, int p) {
    depth[u] = d_val;
    anc[u][0] = p;
    for (const auto& e : dir_graph[u]) {
        int v = e.to;
        if (v != p) {
            dist[v] = dist[u] + e.steps;
            dfs(v, d_val + 1, u);
        }
    }
}

void prepare_lca() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; (1 << j) <= n; ++j) anc[i][j] = -1;
    }
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i <= n; ++i) {
            if (anc[i][j - 1] != -1)
                anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}

int find_lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int shift;
    for (shift = 0; (1 << (shift + 1)) <= depth[u]; ++shift);
    for (int i = shift; i >= 0; --i) {
        if (depth[u] - (1 << i) >= depth[v]) u = anc[u][i];
    }
    if (u == v) return u;
    for (int i = shift; i >= 0; --i) {
        if (anc[u][i] != -1 && anc[u][i] != anc[v][i]) {
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    return anc[u][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> m;
        init();
        for (int i = 1; i < n; ++i) {
            cin >> name1 >> name2;
            if (id_map.find(name1) == id_map.end()) id_map[name1] = ++cnt;
            if (id_map.find(name2) == id_map.end()) id_map[name2] = ++cnt;
            int u = id_map[name1], v = id_map[name2];
            in_deg[u]++;
            dir_graph[u].push_back(DirEdge(v, 1));
            dir_graph[v].push_back(DirEdge(u, 1));
        }
        int root;
        for (int i = 1; i <= n; ++i) {
            if (in_deg[i] == 0) {
                root = i;
                break;
            }
        }
        dfs(root, 0, -1);
        prepare_lca();
        while (m--) {
            cin >> name1 >> name2;
            int u = id_map[name1], v = id_map[name2];
            int lca_node = find_lca(u, v);
            if (lca_node == v) {
                cout << dist[u] - dist[v] << endl;
            } else {
                cout << dist[u] - dist[lca_node] + 1 << endl;
            }
        }
    }
    return 0;
}

Problème 6 : Conception de la ville

Lien : ZOJ 3195

Description : Donné un graphe acyclique, pour chaque groupe de trois régions, calculer la longueur minimale du chemin pour les connecter toutes.

Entrée : Cas multiples. Chaque cas a n régions, n-1 routes, puis Q requêtes de trois régions.

Sortie : Pour chaque requête, la longueur minimale du chemin connectant les trois régions.

Approche : Calculer les distances par paires en utilisant LCA, puis utiliser la formule pour trois nœuds.

Implémentation (C++) :

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int max_regions = 50000 + 7;
int n, q, u, v, w;
int cost[max_regions], depth[max_regions], anc[max_regions][30];

struct Path {
    int end, len;
    Path(int e = 0, int l = 0) : end(e), len(l) {}
};

vector<Path> region_graph[max_regions];

void init_data() {
    memset(cost, 0, sizeof(cost));
    for (int i = 0; i < max_regions; ++i) region_graph[i].clear();
}

void dfs(int node, int d_val, int parent) {
    depth[node] = d_val;
    anc[node][0] = parent;
    for (const auto& p : region_graph[node]) {
        int next = p.end;
        if (next != parent) {
            cost[next] = cost[node] + p.len;
            dfs(next, d_val + 1, node);
        }
    }
}

void preprocess() {
    for (int i = 0; i < n; ++i) {
        for (int j = 1; (1 << j) < n; ++j) anc[i][j] = -1;
    }
    for (int j = 1; (1 << j) < n; ++j) {
        for (int i = 0; i < n; ++i) {
            if (anc[i][j - 1] != -1)
                anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}

int query_lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    int shift;
    for (shift = 0; (1 << shift) <= depth[a]; ++shift);
    for (int i = shift; i >= 0; --i) {
        if (depth[a] - (1 << i) >= depth[b]) a = anc[a][i];
    }
    if (a == b) return a;
    for (int i = shift; i >= 0; --i) {
        if (anc[a][i] != -1 && anc[a][i] != anc[b][i]) {
            a = anc[a][i];
            b = anc[b][i];
        }
    }
    return anc[a][0];
}

int main() {
    bool first_case = true;
    while (scanf("%d", &n) != EOF) {
        if (!first_case) printf("\n");
        first_case = false;
        init_data();
        for (int i = 1; i < n; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            region_graph[u].push_back(Path(v, w));
            region_graph[v].push_back(Path(u, w));
        }
        dfs(0, 0, -1);
        preprocess();
        scanf("%d", &q);
        while (q--) {
            scanf("%d%d%d", &u, &v, &w);
            int lca_ab = query_lca(u, v);
            int lca_ac = query_lca(u, w);
            int lca_bc = query_lca(v, w);
            int dist_ab = cost[u] + cost[v] - 2 * cost[lca_ab];
            int dist_ac = cost[u] + cost[w] - 2 * cost[lca_ac];
            int dist_bc = cost[v] + cost[w] - 2 * cost[lca_bc];
            printf("%d\n", (dist_ab + dist_ac + dist_bc) / 2);
        }
    }
    return 0;
}

Ces problèmes illustrent l'application de l'algorithme LCA dans divers scénarios. Maîtriser ces techniques est essentiel pour résoudre des problèmes de chemin dans les arbres.