Cod sursa(job #2465408)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 30 septembrie 2019 09:08:18
Problema Lowest Common Ancestor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <vector>
#include <fstream>

using namespace std;

ifstream fin ("lca.in");
ofstream fout ("lca.out");

const int MAXN = 3e5 + 5;
int euler[MAXN],nivel[MAXN],ind[MAXN],n,cnt,log[MAXN],rmq[19][MAXN],m;
vector < int > G[MAXN];

void dfs(int x,int niv) {
	
	euler[++cnt] = x,nivel[cnt] = niv,ind[x] = cnt;
	for( auto y : G[x]) {
		dfs(y,niv+1);
		euler[++cnt] = x,nivel[cnt] = niv;
	}
}


void Rmq() {
	
	for ( int i = 1; i <= cnt; ++i)
		rmq[0][i] =i;
	for (int  pw = 1; (1 << pw) <= cnt; ++pw)
		for ( int i = 1; i <= cnt - (1 << pw)+1; ++i)
			if ( nivel[rmq[pw-1][i]] < nivel[rmq[pw-1][i + (1 << (pw-1))]])
				rmq[pw][i] = rmq[pw-1][i];
			else
				rmq[pw][i] = rmq[pw-1][i + (1 << (pw-1)) ];
}

int LCA(int x, int y) {
	
	 x = ind[x];
	 y  = ind[y];
	 if ( x > y)
		swap(x,y);
	int l = log[y-x+1];
	if ( nivel[rmq[l][x]] < nivel[rmq[l][y-(1 <<l) + 1]] )
		return euler[rmq[l][x]];
	return euler[rmq[l][y-(1 <<l) + 1]];
}


int main() {
	
	fin >> n >> m;
	for ( int i = 2,x,y; i <= n; ++i) {
		fin >> y;
		G[y].push_back(i);
	}
	dfs(1,1);
	for ( int i = 2; i <= cnt; ++i)
		log[i] = log[i/2] + 1;
	Rmq();
	for (int x,y; m > 0; --m) {
		fin >> x >> y;
		fout << LCA(x,y) << "\n";
	}
}