Untitled
raw download clone
TEXT
views 15
,
size 1237 b
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int n,q,h[maxn],par[23][maxn],in[maxn],out[maxn],ct;
vector<int> a[maxn];
bool check(int x, int y)
{
    if (in[x]<=in[y]&&out[y]<=out[x])   return true;
    return false;
}
void dfs(int u,int cha)
{
    in[u]=++ct;
    par[0][u]=cha;
    for(int v:a[u])
    {
        if(v==cha)  continue;
        h[v]=h[u]+1;
        dfs(v,u);
    }
    out[u]=ct;
}
int lca(int x, int y)
{
    if(check(x,y)==true)    return x;
    if(check(y,x)==true)    return y;
    for(int i=22;i>=0;i--)
    {
        if(par[i][x]!=0 && check(par[i][x],y)==false)
        {
            x=par[i][x];
        }
    }
    return par[0][x];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<n;i++)
    {
        int v;
        cin>>v;
        a[i+1].push_back(v+1);
        a[v+1].push_back(i+1);
    }
    h[1]=1;
    dfs(1,0);
    for(int i=1;i<=22;i++)  for(int j=1;j<=n;j++)   par[i][j]=par[i-1][par[i-1][j]];
    for(int i=1;i<=q;i++)
    {
        int u,v;
        cin>>u>>v;
        cout<<lca(u+1,v+1)-1<<"\n";
    }
    return 0;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.