Cod sursa(job #368434)

Utilizator Mishu91Andrei Misarca Mishu91 Data 24 noiembrie 2009 21:16:36
Problema Lowest Common Ancestor Scor Ascuns
Compilator cpp Status done
Runda Marime 1.39 kb
#include <vector>
#include <fstream>

using namespace std;

#define MAX_N 100005
#define INF 0x3f3f3f3f

#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)
#define nst (nod << 1)
#define ndr (nst | 1)
#define mij ((li + lf) >> 1)

int K, N, M, P;
int L[MAX_N << 1], H[MAX_N << 1],Lg[MAX_N << 1], First[MAX_N];
int A[MAX_N << 4], st, dr, sol, hsol;

vector <int> G[MAX_N];

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

void citire()
{
	fin >> N >> M;
	
	for(int i = 2; i <= N; ++i)
	{
		int x;
		fin >> x;
		G[x].push_back(i);
	}
}

void dfs(int nod, int lev)
{
	H[++K] = nod; 
	L[K] = lev; 
	First[nod] = K; 

	foreach(G[nod])
	{
		dfs(*it, lev+1);
		
		H[++K] = nod;
		L[K] = lev;
	}
}

void build(int nod, int li, int lf)
{
	if(li == lf)
	{
		A[nod] = li;
		return;
	}

	build(nst, li, mij);
	build(ndr, mij+1, lf);

	if(L[A[nst]] <= L[A[ndr]])
		A[nod] = A[nst];
	else
		A[nod] = A[ndr];
}

void query(int nod, int li, int lf)
{
	if(st <= li && lf <= dr)
	{
		if(L[A[nod]] < hsol)
			sol = H[A[nod]],
			hsol = L[A[nod]];
		return;
	}

	if(st <= mij) query(nst, li, mij);
	if(mij < dr)  query(ndr, mij+1, lf);
}

int lca(int x, int y)
{
	st = First[x], dr = First[y];
	if(st > dr) swap(st, dr);
	sol = hsol = INF;
	query(1, 1, K);

	return sol;
}

int main()
{
	citire();
	dfs(1, 0);
	build(1, 1, K);

	while(M--)
	{
		int x, y;
		fin >> x >> y;
		fout << lca(x, y) << "\n";
	}
}