木構造上の2頂点間の最近共通祖先（Lowest Common Ancestor, LCA）を高速に求めるには、複数のアルゴリズムが存在します。本稿では、倍増法、オイラー巡回＋RMQ、および木の重軽分解（Heavy-Light Decomposition）の3つの代表的手法について、それぞれの設計思想・実装構造・計算量特性を解説します。

倍増法によるLCAクエリ

各頂点から根方向へ2^kステップ先の祖先とそのパス上の重み和を前処理で保持します。クエリ時はまず深さを揃え、その後指数的に近づくことでO(log n)でLCAを特定します。以下は汎用的なテンプレート実装で、型パラメータに対応し、辺重みの累積も可能にしています：

template <typename WeightT>
class BinaryLiftingLCA {
    static constexpr int LOG = 21;
    int n, root;
    std::vector<int> depth;
    std::vector<std::vector<int>> parent;
    std::vector<std::vector<WeightT>> weight_sum;

    struct Edge { int to; WeightT w; };
    std::vector<std::vector<Edge>> graph;

public:
    BinaryLiftingLCA(int node_count, int root_node = 1)
        : n(node_count), root(root_node),
          depth(n + 1), parent(n + 1, std::vector<int>(LOG)),
          weight_sum(n + 1, std::vector<WeightT>(LOG)),
          graph(n + 1) {}

    void add_edge(int u, int v, WeightT w) {
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }

    void build() {
        depth[root] = 0;
        std::vector<bool> visited(n + 1);
        std::function<void(int, int)> dfs = [&](int u, int par) {
            visited[u] = true;
            parent[u][0] = par;
            for (int k = 1; k < LOG; ++k) {
                int anc = parent[u][k-1];
                parent[u][k] = anc ? parent[anc][k-1] : 0;
                weight_sum[u][k] = weight_sum[u][k-1] + 
                                  (anc ? weight_sum[anc][k-1] : WeightT{});
            }
            for (const auto& e : graph[u]) {
                if (e.to != par && !visited[e.to]) {
                    depth[e.to] = depth[u] + 1;
                    weight_sum[e.to][0] = e.w;
                    dfs(e.to, u);
                }
            }
        };
        dfs(root, 0);
    }

    int query(int u, int v) const {
        if (depth[u] < depth[v]) std::swap(u, v);
        // 深さを揃える
        int diff = depth[u] - depth[v];
        for (int k = 0; k < LOG && diff; ++k, diff >>= 1) {
            if (diff & 1) u = parent[u][k];
        }
        if (u == v) return u;
        // 共通祖先へ向かう
        for (int k = LOG - 1; k >= 0; --k) {
            if (parent[u][k] != parent[v][k]) {
                u = parent[u][k];
                v = parent[v][k];
            }
        }
        return parent[u][0];
    }
};

オイラー巡回と区間最小値クエリ

DFSによるオイラー巡回を生成し、訪問順序と対応する深さを記録します。この深さ配列に対してSparse Table（ST表）を構築することで、任意区間の最小深さ位置をO(1)で取得できます。最小深さに対応する頂点がLCAとなります。空間効率と定数時間クエリが特徴です：

class EulerTourLCA {
    int n, root;
    std::vector<std::vector<int>> graph;
    std::vector<int> euler, depth, first_occurrence;
    std::vector<std::vector<int>> st_min_idx;

    void dfs(int u, int d, int& time) {
        first_occurrence[u] = time;
        euler[time] = u;
        depth[time++] = d;
        for (int v : graph[u]) {
            if (v != first_occurrence.size() || first_occurrence[v] == -1) {
                dfs(v, d + 1, time);
                euler[time] = u;
                depth[time++] = d;
            }
        }
    }

public:
    EulerTourLCA(int node_count, int root_node = 1)
        : n(node_count), root(root_node),
          graph(n + 1), euler(2 * n), depth(2 * n),
          first_occurrence(n + 1, -1) {}

    void add_edge(int u, int v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    void build() {
        int time = 0;
        dfs(root, 0, time);
        int len = time;
        // ST表構築（最小深さのインデックス保持）
        st_min_idx.resize(len, std::vector<int>(20));
        for (int i = 0; i < len; ++i) {
            st_min_idx[i][0] = i;
        }
        for (int j = 1; (1 << j) <= len; ++j) {
            for (int i = 0; i + (1 << j) <= len; ++i) {
                int left = st_min_idx[i][j-1];
                int right = st_min_idx[i + (1 << (j-1))][j-1];
                st_min_idx[i][j] = (depth[left] < depth[right]) ? left : right;
            }
        }
    }

    int query(int u, int v) const {
        int l = first_occurrence[u], r = first_occurrence[v];
        if (l > r) std::swap(l, r);
        int k = std::bit_width(static_cast<unsigned int>(r - l + 1)) - 1;
        int idx = (depth[st_min_idx[l][k]] < depth[st_min_idx[r - (1 << k) + 1][k]])
                  ? st_min_idx[l][k] : st_min_idx[r - (1 << k) + 1][k];
        return euler[idx];
    }
};

重軽分解によるLCA

各ノードの最大部分木サイズに基づき「重子」を定義し、重子を辿るパスを「重鎖」として分割します。クエリ時は、異なる重鎖に属する場合、深い方のトップを親に移動させることでO(log n)ステップでLCAに到達します。線形空間かつ実用的な定数性能が利点です：

class HeavyLightLCA {
    int n, root;
    std::vector<std::vector<int>> graph;
    std::vector<int> parent, depth, size, heavy, top;

    void dfs1(int u, int p) {
        parent[u] = p;
        size[u] = 1;
        depth[u] = depth[p] + 1;
        int max_subtree = 0;
        for (int v : graph[u]) {
            if (v == p) continue;
            dfs1(v, u);
            size[u] += size[v];
            if (size[v] > max_subtree) {
                max_subtree = size[v];
                heavy[u] = v;
            }
        }
    }

    void dfs2(int u, int head) {
        top[u] = head;
        if (heavy[u] != -1) {
            dfs2(heavy[u], head);
        }
        for (int v : graph[u]) {
            if (v != parent[u] && v != heavy[u]) {
                dfs2(v, v);
            }
        }
    }

public:
    HeavyLightLCA(int node_count, int root_node = 1)
        : n(node_count), root(root_node),
          graph(n + 1), parent(n + 1), depth(n + 1),
          size(n + 1), heavy(n + 1, -1), top(n + 1) {}

    void add_edge(int u, int v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    void build() {
        depth[0] = -1;
        dfs1(root, 0);
        dfs2(root, root);
    }

    int query(int u, int v) const {
        while (top[u] != top[v]) {
            if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
            u = parent[top[u]];
        }
        return depth[u] < depth[v] ? u : v;
    }
};