src/tree/lca.hpp

View this file on GitHub
Last update: 2026-02-20 11:11:46+09:00
Include: #include "src/tree/lca.hpp"

Depends on

Verified with

src/test/yosupo_lca.cpp

Code

#include "../template.hpp"
#include "../structure/sparsetable.hpp"

struct LCA {
    vector<vector<int>> G;
    int N;
    vector<int> in,dep,ord;
    SparseTable<pair<int,int>> st;
    LCA(vector<vector<int>> G_,int root=0):G(G_),N(si(G)),in(N),dep(N){
        dep[root]=0;
        dfs2(root);
        vector<pair<int,int>> a(si(ord));
        rep(i,si(ord)) a[i]=make_pair(dep[ord[i]],ord[i]);
        st=SparseTable<pair<int,int>>(a);
    }
    void dfs2(int v){
        in[v]=si(ord);
        ord.push_back(v);
        for(auto& e: G[v]){
            dfs2(e);
            ord.push_back(v);
        }
    }
    int lca(int u,int v){
        if(in[u]>in[v]) swap(u,v);
        return st.prod(in[u],in[v]+1).se;
    }
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/structure/sparsetable.hpp"

template<typename T> struct SparseTable {
    function<T(T,T)> f;
    vector<vector<T>> st;
    SparseTable(const vector<T> v={T{}},
                const function<T(T,T)>& f_=[] (T a,T b){return min(a,b);}):
        f(f_){
        int n=si(v);
        int l=32-__builtin_clz(n);
        st.resize(l,vector<T>(n));
        st[0]=v;
        rep(k,l-1){
            rep(i,n-(1<<(k+1))+1){st[k+1][i]=f(st[k][i],st[k][i+(1<<k)]);}
        }
    }
    T prod(int l,int r){
        int k=31-__builtin_clz(r-l);
        return f(st[k][l],st[k][r-(1<<k)]);
    }
};
#line 3 "src/tree/lca.hpp"

struct LCA {
    vector<vector<int>> G;
    int N;
    vector<int> in,dep,ord;
    SparseTable<pair<int,int>> st;
    LCA(vector<vector<int>> G_,int root=0):G(G_),N(si(G)),in(N),dep(N){
        dep[root]=0;
        dfs2(root);
        vector<pair<int,int>> a(si(ord));
        rep(i,si(ord)) a[i]=make_pair(dep[ord[i]],ord[i]);
        st=SparseTable<pair<int,int>>(a);
    }
    void dfs2(int v){
        in[v]=si(ord);
        ord.push_back(v);
        for(auto& e: G[v]){
            dfs2(e);
            ord.push_back(v);
        }
    }
    int lca(int u,int v){
        if(in[u]>in[v]) swap(u,v);
        return st.prod(in[u],in[v]+1).se;
    }
};