Pagini recente » Cod sursa (job #757037) | Istoria paginii runda/3271c72e82/clasament | Cod sursa (job #533028) | Istoria paginii runda/brasov_16/clasament | Cod sursa (job #2395660)
#include <bits/stdc++.h>
using namespace std;
ifstream in("lca.in");
ofstream out("lca.out");
const int DIM = 1e5 + 7;
vector <int> v[DIM];
int f[DIM];
int niv[DIM];
int rmq[20][2 * DIM];
int query(int a, int b)
{
if(a > b)
swap(a, b);
int bit = log2(b - a + 1);
if(niv[rmq[bit][a]] < niv[rmq[bit][b - (1 << bit) + 1]])
return rmq[bit][a];
else
return rmq[bit][b - (1 << bit) + 1];
}
int p = 0;
void dfs(int nod, int lvl = 1, int dad = 0)
{
niv[nod] = lvl;
rmq[0][++p] = nod;
f[nod] = p;
for(auto i : v[nod])
if(i != dad)
{
dfs(i, lvl + 1, nod);
rmq[0][++p] = nod;
}
}
int main()
{
int n, q;
in >> n >> q;
for(int i = 2; i <= n; i++)
{
int x;
in >> x;
v[x].push_back(i);
}
dfs(1);
for(int bit = 1; (1 << bit) <= p; bit++)
for(int j = 1; j + (1 << bit) - 1 <= p; j++)
if(niv[rmq[bit - 1][j]] < niv[rmq[bit - 1][j + (1 << (bit - 1))]])
rmq[bit][j] = rmq[bit - 1][j];
else
rmq[bit][j] = rmq[bit - 1][j + (1 << (bit - 1))];
while(q--)
{
int x, y;
in >> x >> y;
out << query(f[x], f[y]) << '\n';
}
}