Pagini recente » Cod sursa (job #1948439) | Borderou de evaluare (job #496090) | Cod sursa (job #2103796)
#include <bits/stdc++.h>
#define dbg(x) cerr<<#x": "<<x<<"\n"
using namespace std;
ifstream fin("lca.in");
ofstream fout("lca.out");
vector<int> v[100010];
int nivel[200010],euler[200010],i,j;
int rmq[20][200010],first[100010],l2[200010];
void dfs(int nod, int niv)
{
first[nod]=euler[0]+1;
for (auto i:v[nod])
{
euler[++euler[0]]=nod;
nivel[++nivel[0]]=niv;
dfs(i,niv+1);
}
euler[++euler[0]]=nod;
nivel[++nivel[0]]=niv;
}
int main()
{
ios_base::sync_with_stdio(0);
int x,i,n,m,y;
fin>>n>>m;
for (i=2;i<=2*n;i++)
{
l2[i]=l2[i/2]+1;
}
for (i=2;i<=n;i++)
{
fin>>x;
v[x].push_back(i);
}
dfs(1,1);
for (i=1;i<=euler[0];i++)
rmq[0][i]=i;
for (i=1;(1<<i)<=euler[0];i++)
{
for (j=1;j+(1<<i)-1<=euler[0];j++)
{
if (nivel[rmq[i-1][j]]<nivel[rmq[i-1][j+(1<<(i-1))]])
rmq[i][j]=rmq[i-1][j];
else rmq[i][j]=rmq[i-1][j+(1<<(i-1))];
}
}
for (i=1;i<=m;i++)
{
fin>>x>>y;
if(first[x] > first[y]) swap(x, y);
int l = l2[first[y]-first[x]+1];
if (nivel[rmq[l][first[x]]]<nivel[rmq[l][first[y]-(1<<l)+1]])
fout<<euler[rmq[l][first[x]]]<<'\n';
else fout<<euler[rmq[l][first[y]-(1<<l)+1]]<<'\n';
}
}