Cod sursa(job #578723)
#include <fstream>
#include <vector>
using namespace std;
const int N=100001,LG=18;
int v[2*N],rmq[2*N][LG],level[N],poz[N],n;
vector<int> a[N];
ifstream in("lca.in");
ofstream out("lca.out");
inline int best(int a,int b)
{
return level[a]<level[b] ? a : b;
}
void dfs(int x,int lvl)
{
level[x]=lvl;
v[++v[0]]=x;
for (unsigned int i=0;i<a[x].size();i++)
{
int y=a[x][i];
dfs(y,lvl+1);
v[++v[0]]=x;
}
}
inline int query(int x,int y)
{
int p,q;
for (p=0,q=1;q<=y;p++,q<<=1);
p--;q>>=1;
return best(rmq[x][p],rmq[x+q-1][p]);
}
int main()
{
int t,i,j,k,x,y;
in>>n>>t;
for (i=2;i<=n;i++)
{
in>>x;
a[x].push_back(i);
}
dfs(1,0);
for (i=v[0];i;i--)
{
rmq[i][0]=v[i];
for (j=k=1;i+(k<<1)<=v[0]+1;j++,k<<=1)
rmq[i][j]=best(rmq[i][j-1],rmq[i+k][j-1]);
}
for (i=v[0];i;i--)
poz[v[i]]=i;
level[0]=1<<30;
while (t--)
{
in>>x>>y;x=poz[x];y=poz[y];
if (x>y)
{
int aux=x;
x=y;
y=aux;
}
out<<query(x,y-x+1)<<"\n";
}
return 0;
}