Pagini recente » Cod sursa (job #2286591) | Cod sursa (job #796919) | Cod sursa (job #1029898) | Cod sursa (job #2368385)
#include <bits/stdc++.h>
using namespace std;
ifstream f("lca.in");
ofstream g("lca.out");
const int N = 1<<17;
int n, q,k,niv[N],T[N],pa[N],rmq[18][2*N];
vector<int> v[N];
void dfs(int);
int main()
{
f>>n>>q;
for(int i=2;i<=n;i++)
{
int j;
f>>j;
T[i]=j;
v[j].push_back(i);
}
dfs(1);
for(int p=1,P=2,i=1;P<=k;p<<=1,P<<=1,i++)
for(int st=1,mi=p+1,dr=P;dr<=k;st++,mi++,dr++)
rmq[i][st]=niv[rmq[i-1][st]]<niv[rmq[i-1][mi]]?rmq[i-1][st]:rmq[i-1][mi];
for(;q;q--)
{
int x,y,lg;
f>>x>>y;
x=pa[x];
y=pa[y];
if(x>y)swap(x,y);
lg=y-x+1;
int i=31-__builtin_clz(lg);
lg=1<<i;
y=y-lg+1;
if(niv[rmq[i][y]]<niv[rmq[i][x]])
x=y;
g<<rmq[i][x]<<'\n';
}
return 0;
}
void dfs(int nod)
{
rmq[0][++k]=nod;
niv[nod]=niv[T[nod]]+1;
pa[nod]=k;
for(auto fiu:v[nod])
{
dfs(fiu);
rmq[0][++k]=nod;
}
}