Cod sursa(job #369688)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 29 noiembrie 2009 11:24:25
Problema Lowest Common Ancestor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
#define N 1<<17
#define P 1<<18
using namespace std;
int n,m,r;
vector <int> v[N];
int ap[N],euler[P],grd[N],nivel[P],lg[P];
int rmq[20][P];
char marc[N];
ifstream in("lca.in");
ofstream out("lca.out");
void read()
{
	in>>n>>m;
	int i,x;
	for (i=1; i<n; i++)
	{
		in>>x;
		v[x].push_back(i+1);
	}
}
inline int min(int a,int b)
{
	if (grd[a]<grd[b])
		return a;
	return b;
}
void dfs(int nod)
{
	int i;
	marc[nod]=1;
	for (i=0; i<v[nod].size(); i++)
		if (!marc[v[nod][i]])
		{
			euler[++r]=v[nod][i];
			if (!ap[v[nod][i]])
				ap[v[nod][i]]=r;
			grd[v[nod][i]]=grd[nod]+1;
			dfs(v[nod][i]);
			euler[++r]=nod;
		}
}
void make_rmq()
{
	int i,j,t,k;
	for (i=1; i<=r; i++)
	{
		lg[i]=i>=2 ? lg[i/2]+1 : 0;
		rmq[0][i]=euler[i];
	}
	for (i=1; (1<<i)<=r; i++)
	{
		t=1<<i;
		k=1<<(i-1);
		for (j=1; j<=r-t+1; j++)
			rmq[i][j]=min(rmq[i-1][j],rmq[i-1][(j+t-1)-k+1]);
	}
}
void queries()
{
	int i,x,y,t,l;
	for (i=1; i<=m; i++)
	{
		in>>x>>y;
		x=ap[x];
		y=ap[y];
		if (x>y){
			t=x;  x=y;  y=t;
		}
		l=lg[y-x+1];
		t=1<<l;
		out<<min(rmq[l][x],rmq[l][y-t+1])<<'\n';
	}
}
int main()
{
	read();
	euler[++r]=1;
	ap[1]=1;
	dfs(1);
	make_rmq();
	queries();
	return 0;
}