src/test/yosupo_lca.cpp

• View this file on GitHub
• Last update: 2026-02-20 11:11:46+09:00
• Problem: https://judge.yosupo.jp/problem/lca

Depends on

• src/structure/sparsetable.hpp
• src/template.hpp
• src/tree/lca.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#include "../tree/lca.hpp"

int main(){
    int N,Q;
    cin>>N>>Q;
    vector<vector<int>> G(N);
    rep(i,N-1){
        int p;
        cin>>p;
        G[p].push_back(i+1);
    }
    LCA lca(G);
    while(Q--){
        int u,v;
        cin>>u>>v;
        cout<<lca.lca(u,v)<<"\n";
    }
}

#line 1 "src/test/yosupo_lca.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#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;
    }
};
#line 4 "src/test/yosupo_lca.cpp"

int main(){
    int N,Q;
    cin>>N>>Q;
    vector<vector<int>> G(N);
    rep(i,N-1){
        int p;
        cin>>p;
        G[p].push_back(i+1);
    }
    LCA lca(G);
    while(Q--){
        int u,v;
        cin>>u>>v;
        cout<<lca.lca(u,v)<<"\n";
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	1985 ms	279 MB
g++	almost_line_01	AC	1982 ms	279 MB
g++	binary_00	AC	2003 ms	249 MB
g++	binary_01	AC	2004 ms	250 MB
g++	binary_02	AC	2009 ms	249 MB
g++	example_00	AC	6 ms	4 MB
g++	line_00	AC	1537 ms	250 MB
g++	line_01	AC	1805 ms	296 MB
g++	line_02	AC	290 ms	35 MB
g++	line_03	AC	1561 ms	275 MB
g++	line_04	AC	1018 ms	179 MB
g++	max_line_00	AC	1969 ms	320 MB
g++	max_line_01	AC	1989 ms	320 MB
g++	max_line_02	AC	1973 ms	320 MB
g++	max_random_00	AC	1996 ms	250 MB
g++	max_random_01	AC	1999 ms	250 MB
g++	max_random_02	AC	1989 ms	250 MB
g++	path_graph_root_centroid_00	AC	1935 ms	296 MB
g++	path_graph_root_centroid_01	AC	1935 ms	296 MB
g++	path_graph_root_centroid_02	AC	1934 ms	296 MB
g++	random_00	AC	1557 ms	196 MB
g++	random_01	AC	1846 ms	232 MB
g++	random_02	AC	291 ms	27 MB
g++	random_03	AC	1578 ms	215 MB
g++	random_04	AC	1026 ms	140 MB

Back to top page