Pagini recente » Diferente pentru problema/dreptunghiuri3 intre reviziile 4 si 6 | Borderou de evaluare (job #2547151) | Auto | Borderou de evaluare (job #3217844) | Cod sursa (job #2396628)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin("lca.in");
ofstream fout("lca.out");
#define For(i, a, b) for(i = (a); i <= (b); i++)
#define NMax 100010
#define LMax 20
int n, m;
int h[NMax << 1], l[NMax << 1], lg[NMax << 1], First[NMax];
int k = -1;
int rmq[NMax << 2][LMax];
vector<int> G[NMax];
void dfs(int x, int lev);
void init_rmq();
int lca(int, int);
int main(){
int i, x, y;
fin >> n >> m;
For(i, 2, n){
fin >> x;
G[x].push_back(i);
}
dfs(1, 0);
// For(i, 0, k) cout << h[i] << ' ';
// cout << endl;
// For(i, 0, k) cout << l[i] << ' ';
// cout << endl;
init_rmq();
while(m--){
fin >> x >> y;
fout << lca(x, y) << '\n';
}
}
void dfs(int x, int lev){
h[++k] = x;
l[k] = lev;
First[x] = k;
for(int i = 0; i < G[x].size(); i++){
dfs(G[x][i], lev + 1);
h[++k] = x;
l[k] = lev;
}
}
void init_rmq(){
int i, j, m;
For(i, 0, k) rmq[i][0] = i;
for(j = 1; (1 << j) <= k; j++){
for(i = 0; i + (1 << j) - 1 <= k; i++)
if(l[rmq[i][j - 1]] < l[rmq[i + (1 << (j - 1))][j - 1]])
rmq[i][j] = rmq[i][j - 1];
else
rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1];
}
}
int lca(int a, int b){
int poz;
a = First[a];
b = First[b];
if(a > b) swap(a, b);
int lg = (int)log2(b - a + 1);
if(l[rmq[a][lg]] < l[rmq[b - (1 << lg) + 1][lg]]) poz = rmq[a][lg];
else poz = rmq[b - (1 << lg) + 1][lg];
return h[poz];
}