Cod sursa(job #368664)

Utilizator Mishu91Andrei Misarca Mishu91 Data 25 noiembrie 2009 12:37:12
Problema Lowest Common Ancestor Scor Ascuns
Compilator cpp Status done
Runda Marime 1.12 kb
#include <fstream>
#include <vector>

using namespace std;

#define MAX_N 100005
#define MAX_L 20

#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)

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

int N, M, Lmax, T[MAX_L][MAX_N], Lg[MAX_N], Lev[MAX_N];
vector <int> G[MAX_N];

void citire()
{
	fin >> N >> M;

	for(int i = 2; i <= N; ++i)
	{
		fin >> T[0][i];
		G[T[0][i]].push_back(i);
	}

	int k;
	for(k = 1; (1 << k) <= N; ++k)
		for(int i = 1; i <= N; ++i)
			T[k][i] = T[k-1][T[k-1][i]];
	Lev[0] = -1;
}

void dfs(int nod, int lev)
{
	Lev[nod] = lev;
	if(Lmax < lev) Lmax = lev;

	foreach(G[nod])
		dfs(*it, lev+1);
}

int lca(int x, int y)
{
	if(Lev[x] < Lev[y])
		swap(x, y);

	for(int k = Lmax; k; --k)
		if(Lev[T[k-1][x]] >= Lev[y])
			x = T[k-1][x];

	for(int k = Lmax; k; --k)
		if(T[k-1][x] != T[k-1][y])
			x = T[k-1][x],
			y = T[k-1][y];
		
	if(x != y) return T[0][x];
	return x;
}

int main()
{
	citire();
	dfs(1, 0);
	for(; (Lmax & (Lmax - 1)); --Lmax);

	int k = 0;
	for(; Lmax != 1; ++k, Lmax >>= 1);
	Lmax = k;

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