Pagini recente » Cod sursa (job #1839382) | Cod sursa (job #636994) | Cod sursa (job #536406) | Cod sursa (job #158929) | Cod sursa (job #737659)
Cod sursa(job #737659)
#include <fstream>
#include <stdlib.h>
#include <cmath>
using namespace std;
ifstream f("lca.in");
ofstream g("lca.out");
int n, m, vector[100001], nrRam[100001], euler[100001 * 2][2], pozitie = 0;
int M[100001][1000];
int lg = 0, poz[100001 * 2];
void eulerFunction(int nr, int h){
euler[pozitie][0] = nr;
euler[pozitie++][1] = h;
for(int i = 2; i <= n; i++) {
if(vector[i] == nr) {
eulerFunction(i, h + 1);
euler[pozitie][0] = nr;
euler[pozitie++][1] = h;
}
}
}
void procesare() {
int i,j;
for(int i = 0; i < 2*n-1; i++) {
M[i][0]=i;
}
for(j = 1; 1 << j <= 2*n-1; j++)
for(i = 0; i + (1 << j) - 1 < 2 * n-1; i++)
if(euler[M[i][j-1]][1] < euler[M[i+(1<<(j-1))][j-1]][1])
M[i][j]=M[i][j-1];
else
M[i][j]=M[i+(1<<(j-1))][j-1];
for(int i=0;i<2*n-1;i++)
poz[euler[i][0]] = i;
}
int rmq(int i, int j) {
int k = (int)log2(j-i+1);
if(euler[M[i][k]][1] <= euler[M[j-(1<<k)+1][k]][1])
return euler[M[i][k]][0];
else
return euler[M[j-(1<<k)+1][k]][0];
}
int query(int i, int j){
int u, v;
if(poz[i] < poz[j]){
u = poz[i];
v = poz[j];
}
else {
u = poz[j];
v = poz[i];
}
return rmq(u, v);
}
int main(){
int a, b;
f >> n >> m;
for(int i = 1; i <= n ; i++){
nrRam[i] = 0;
}
for(int i = 2; i <= n ; i++){
f >> vector[i];
nrRam[vector[i]]++;
}
eulerFunction(1, 0);
procesare();
for(int i = 0; i < m; i++) {
f >> a;
f >> b;
g << query(a, b) << endl;
}
return 0;
}