# Cod sursa(job #928089)

Utilizator Data 26 martie 2013 11:20:39 Lowest Common Ancestor 60 cpp done Arhiva educationala 1.18 kb
``````#include<fstream>
#include<vector>
using namespace std;
ofstream g("lca.out");
int n,m,i,j,t[200001],ap[100001],b[400001],niv[400001],nr,lg[200001];
vector<int>a[100001];
int rmq[20][400001],x,y;
void df(int x,int l)
{
b[++nr]=x;
niv[nr]=l;
ap[x]=nr;
for(int i=0;i<a[x].size();++i)
{
df(a[x][i],l+1);
b[++nr]=x;
niv[nr]=l;
}
}
int lca(int x, int y)
{
int sol,a,b,dif,l;
a=ap[x];
b=ap[y];
if(a>b)
swap(a,b);
dif=b-a+1;
l=lg[dif];
sol=rmq[l][a];
if(niv[sol]>niv[rmq[l][a+dif-(1<<l)]])
sol=rmq[l][a+dif-(1<<l)];

return sol;
}
int main()
{
ifstream f("lca.in");

f>>n>>m;
for(i=2;i<=n;++i)
{
f>>t[i];
a[t[i]].push_back(i);
}
df(1,1);
lg[1]=0;
for(i=2;i<=nr;++i)
lg[i]=lg[i>>1]+1;

for(i=1;i<=nr;++i)
rmq[0][i]=i;

for(i=1;(1<<i)<nr;++i)
for(j=1;j<nr-(1<<i);++j)
{
rmq[i][j]=rmq[i-1][j];
if(niv[rmq[i][j]]>niv[ rmq[i-1][j+(1<<i-1)] ])
rmq[i][j]=rmq[i-1][j+(1<<i-1)];
}
while(m--)
{
f>>x>>y;
g<<b[lca(x,y)]<<"\n";
}
return 0;
}
``````