Cod sursa(job #2395660)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 2 aprilie 2019 19:22:23
Problema Lowest Common Ancestor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#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';
	}
}