Pagini recente » Cod sursa (job #2071588) | Cod sursa (job #1389140) | Cod sursa (job #1298917) | Cod sursa (job #1067698) | Cod sursa (job #2638939)
#include <bits/stdc++.h>
using namespace std;
ifstream in("lca.in");
ofstream out("lca.out");
const int lim=1e5+4;
vector<int> vec[lim];
pair<int,int> tree[18][2*lim];
int poz[lim],cnt;
int lg[2*lim];
void df(int nod,int h)
{
++cnt;
poz[nod]=cnt;
tree[0][cnt]={h,nod};
for(int x:vec[nod])
{
df(x,h+1);
++cnt;
poz[nod]=cnt;
tree[0][cnt]={h,nod};
}
}
void rmq()
{
for(int i=2;i<=cnt;++i)
lg[i]=lg[i/2]+1;
for(int p=1;p<=lg[cnt];++p)
for(int i=1;i+(1<<p)<=cnt+1;++i)
tree[p][i]=min(tree[p-1][i],tree[p-1][i+(1<<(p-1))]);
}
int ans(int x,int y)
{
x=poz[x];
y=poz[y];
if(x>y) swap(x,y);
int d=lg[y-x+1];
return min(tree[d][x],tree[d][y-(1<<d)+1]).second;
}
int main()
{
int n,q,x,y;
in>>n>>q;
for(int i=2;i<=n;++i)
in>>x,vec[x].push_back(i);
df(1,1);
rmq();
while(q--)
{
in>>x>>y;
out<<ans(x,y)<<'\n';
}
return 0;
}