Pagini recente » Borderou de evaluare (job #2543481) | Cod sursa (job #2589116) | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #2426311)
#include <bits/stdc++.h>
#define dbg(x) cerr<<#x": "<<x<<"\n"
using namespace std;
ifstream fin("lca.in");
ofstream fout("lca.out");
vector<int> v[100010], euler, nivel;
int rmq[20][200010],first[100010],l2[200010];
void dfs(int nod, int niv)
{
first[nod] = euler.size();
for (auto i : v[nod]) {
euler.push_back(nod);
nivel.push_back(niv);
dfs(i, niv+1);
}
euler.push_back(nod);
nivel.push_back(niv);
}
int LCA(int x, int y) {
if(first[x] > first[y])
swap(x, y);
int l = l2[first[y]-first[x]+1];
if (nivel[rmq[l][first[x]]] < nivel[rmq[l][first[y]-(1<<l)+1]])
return euler[rmq[l][first[x]]];
return euler[rmq[l][first[y]-(1<<l)+1]];
}
int main()
{
ios_base::sync_with_stdio(0);
int x,n,m,y;
fin>>n>>m;
for (int i=2;i<=2*n;i++)
l2[i]=l2[i/2]+1;
for (int i=2;i<=n;i++) {
fin>>x;
v[x].push_back(i);
}
dfs(1,1);
for (int i = 0;i < euler.size();i++)
rmq[0][i] = i;
for (int i = 1;(1<<i) < euler.size();i++)
for (int j = 0; j + (1 << i)-1 < euler.size(); j++)
if (nivel[rmq[i-1][j]]<nivel[rmq[i-1][j+(1<<(i-1))]])
rmq[i][j] = rmq[i - 1][j];
else
rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
for(int i = 1; i <= m; i++) {
fin >> x >> y;
fout << LCA(x, y) << '\n';
}
}