Company Queries II

#include <bits/stdc++.h>
using namespace std;
const int N=200005,LOG=20;
int up[N][LOG+1],d[N];
vector<int> g[N];
void dfs(int u){
    for(int v:g[u]){d[v]=d[u]+1;up[v][0]=u;
        for(int j=1;j<=LOG;j++)up[v][j]=up[up[v][j-1]][j-1];
        dfs(v);
    }
}
int lca(int a,int b){
    if(d[a]<d[b])swap(a,b);
    for(int j=LOG;j>=0;j--)if(d[a]-(1<<j)>=d[b])a=up[a][j];
    if(a==b)return a;
    for(int j=LOG;j>=0;j--)if(up[a][j]!=up[b][j])a=up[a][j],b=up[b][j];
    return up[a][0];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=2;i<=n;i++){int e;cin>>e;g[e].push_back(i);}
    dfs(1);
    while(q--){int a,b;cin>>a>>b;cout<<lca(a,b)<<'\n';}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED