Artifact df81a86e707e972b64432cf012947003249a8816
//-------------------------------------------------------------
// The Least Common Ancestor
//
// Verified by
// - ICPC 2021 Yokohama Regional I
//-------------------------------------------------------------
template<int K=17>
struct Lca
{
const int N;
const vector<int>& depth;
vector<vector<int>> jump;
Lca(int N, const vector<int>& parent, const vector<int>& depth)
: N(N), depth(depth), jump(K, vector<int>(N, -1))
{
jump[0] = parent;
for(int k=0; k+1<K; ++k)
for(int v=0; v<N; ++v)
if(jump[k][v] != -1)
jump[k+1][v] = jump[k][jump[k][v]];
}
int operator()(int a, int b) const {
if(depth[a]>depth[b]) swap(a,b);
for(int k=0; k<K; ++k)
if((depth[b]-depth[a]) & (1<<k))
b = jump[k][b];
if(a == b)
return a;
for(int k=K-1; k>=0; --k)
if(jump[k][a] != jump[k][b]) {
a = jump[k][a];
b = jump[k][b];
}
return jump[0][a];
}
};