Pagini recente » Cod sursa (job #3209649) | Cod sursa (job #1339907) | Cod sursa (job #2525454) | Cod sursa (job #319187) | Cod sursa (job #2475006)
#include <bits/stdc++.h>
using namespace std;
ifstream f("lca.in");
ofstream g("lca.out");
int E[200005],L[200005], Oc[100005], M[100005][20],Min_node[100005][20];
int nr,n,q,i,x;
vector<int> A[100005];
int log(int n)
{
int p = 1;
int nr = 0;
while(p<=n)
{
nr++;
p*=2;
}
return nr;
}
void dfs(int nod, int level)
{
nr++;
if(Oc[nod] == 0)
Oc[nod] = nr;
E[nr] = nod;
L[nr] = level;
for(int x:A[nod])
{
dfs(x,level+1);
nr++;
E[nr] = nod;
L[nr] = level;
}
}
void preproc_rmq()
{
int i,j;
for(i=1;i<=2*n-1;i++){
Min_node[i][0] = E[i];
M[i][0] = L[i];
}
for(j=1;(1<<j) <=2*n-1;j++)
{
for(i=1; i + (1<<(j-1)) - 1 <=2*n-1; i++){
M[i][j] = M[i][j-1];
Min_node[i][j] = Min_node[i][j-1];
if(M[i][j] > M[i+(1<<(j-1)) -1][j-1])
{
M[i][j] = M[i+(1<<(j-1)) -1][j-1];
Min_node[i][j] = Min_node[i+(1<<(j-1)) -1][j-1];
}
}
}
}
int rmq(int l, int r)
{
l = Oc[l];
r = Oc[r];
int len = log(r-l+1);
if(M[l][len]<= M[r-(1<<len)+1][len])
return Min_node[l][len];
else
return Min_node[r-(1<<len)+1][len];
}
int main()
{
f>>n>>q;
for(i=1;i<=n-1;i++)
{
f>>x;
A[x].push_back(i+1);
}
dfs(1,0);
preproc_rmq();
int l,r;
int j;
for(i=1;i<=q;i++){
f>>l>>r;
g<<rmq(l,r)<<'\n';
}
return 0;
}