Pagini recente » Istoria paginii runda/summer | Cod sursa (job #658850) | Cod sursa (job #469543) | Cod sursa (job #1715464) | Cod sursa (job #403731)
Cod sursa(job #403731)
#include<fstream.h>
int n,m,eu[200000],niv[200000],ver[100000],leg[100000],padre[100000],rmq[18][200000],lg[200000],beg[100000];
void dfs(int nod, int nivel)
{
eu[++eu[0]]=nod;
niv[eu[0]]=nivel;
if(!beg[nod])
beg[nod]=eu[0];
int t=lg[nod];
while(t)
{
dfs(ver[t],nivel+1);
t=leg[t];
}
if(padre[nod])
{
eu[++eu[0]]=padre[nod];
niv[eu[0]]=nivel-1;
}
}
int main()
{
int x,i,y,j,l;
ifstream f("lca.in");
ofstream g("lca.out");
f>>n>>m;
for(i=2;i<=n;i++)
{
f>>x;
padre[i]=x;
ver[i-1]=i;
leg[i-1]=lg[x];
lg[x]=i-1;
}
dfs(1,0);
lg[1]=0;
for(i=2;i<=eu[0];i++)
lg[i]=lg[i>>1]+1;
for(i=1;i<=eu[0];i++)
rmq[0][i]=i;
for(j=1;j<=lg[eu[0]];j++)
for(i=1;j<=lg[eu[0]+1-i];i++)
if(niv[rmq[j-1][i]]<niv[rmq[j-1][i+(1<<(j-1))]])
rmq[j][i]=rmq[j-1][i];
else
rmq[j][i]=rmq[j-1][i+(1<<(j-1))];
while(m--)
{
f>>x>>y;
x=beg[x];
y=beg[y];
if(x>y)
{
n=x;
x=y;
y=n;
}
l=lg[y-x+1];
if(niv[rmq[l][x]]<niv[rmq[l][y-(1<<l)+1]])
g<<eu[rmq[l][x]]<<'\n';
else
g<<eu[rmq[l][y-(1<<l)+1]]<<'\n';
}
return 0;
}