Pagini recente » Cod sursa (job #574756) | Istoria paginii utilizator/tianainfo | Cod sursa (job #1462949) | Cod sursa (job #106589) | Cod sursa (job #1838331)
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <climits>
using namespace std;
int A[100000];
int E[500000];
int H[500000];
int Father[100000];
vector<int> Ch[100000];
int n, m;
int pos_euler;
int B[500005];
int N;
int lung_bloc, nr_bloc;
void calcMin(){
int j = 0;
int minim = 0;
for(int i=0; i<nr_bloc; i++){
minim = H[j];
for(int k=0; k<lung_bloc; k++){
if(H[j] < minim)
minim = H[j];
j++;
}
B[i] = minim;
}
}
int query(int st, int dr){
int minim = H[st];
while((st % lung_bloc)!=0 && (st <= dr)){
if(H[st] < minim)
minim = H[st];
st++;
}
while(((dr+1)%lung_bloc!=0) && (dr > st)){
if(H[dr] < minim)
minim = H[dr];
dr--;
}
int st_bloc = st/lung_bloc;
int dr_bloc = dr/lung_bloc;
if((st % lung_bloc==0) && (dr - st+1) >= lung_bloc )
for(int i=st_bloc; i<=dr_bloc; i++)
if(B[i] < minim)
minim = B[i];
return minim;
}
void parcurgere_euleriana(int nod, int h){
queue<int> Q;
Q.push(nod);
E[pos_euler] = nod;
H[pos_euler] = h;
pos_euler++;
while(!Q.empty()){
int nod = Q.front();
for(vector<int>::iterator it = Ch[nod].begin(); it!=Ch[nod].end(); it++){
parcurgere_euleriana(*it, h+1);
E[pos_euler] = nod;
H[pos_euler] = h;
pos_euler++;
}
Q.pop();
}
}
void afisEuler(){
for(int i=0; i<pos_euler; i++)
cout << E[i] << " ";
cout << endl;
cout << "H:" << endl;
for(int i=0; i<pos_euler; i++)
cout << H[i] << " ";
cout << endl;
}
int minimEuler(int a, int b){
int i=0;
int pos_a = pos_euler;
int pos_b = pos_euler;
while(i < pos_euler && (pos_a == pos_euler || pos_b == pos_euler)){
if(E[i] == a)
pos_a = i;
if(E[i] == b)
pos_b = i;
i++;
}
if(pos_a > pos_b)
swap(pos_a, pos_b);
int minim = query(pos_a, pos_b);
for(int i=pos_a; i<=pos_b; i++)
if(H[i] == minim)
return i;
}
int main()
{
freopen("lca.in", "r", stdin);
freopen("lca.out", "w", stdout);
scanf("%d %d", &n, &m);
for(int i=1; i<n; i++)
{
cin >> A[i];
Ch[A[i]].push_back(i+1);
Father[i+1] = A[i];
}
parcurgere_euleriana(1, 0);
// afisEuler();
N = pos_euler;
lung_bloc = sqrt(N);
nr_bloc = N/lung_bloc;
calcMin();
int a, b;
for(int i=0; i<m; i++){
scanf("%d %d", &a, &b);
printf("%d\n", E[minimEuler(a, b)] );
}
return 0;
}