Cod sursa(job #578723)

Utilizator mihai995mihai995 mihai995 Data 11 aprilie 2011 15:35:08
Problema Lowest Common Ancestor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
using namespace std;

const int N=100001,LG=18;
int v[2*N],rmq[2*N][LG],level[N],poz[N],n;
vector<int> a[N];

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

inline int best(int a,int b)
{
	return level[a]<level[b] ? a : b;
}

void dfs(int x,int lvl)
{
	level[x]=lvl;
	v[++v[0]]=x;
	for (unsigned int i=0;i<a[x].size();i++)
	{
		int y=a[x][i];
		dfs(y,lvl+1);
		v[++v[0]]=x;
	}
}

inline int query(int x,int y)
{
	int p,q;
	for (p=0,q=1;q<=y;p++,q<<=1);
	p--;q>>=1;
	return best(rmq[x][p],rmq[x+q-1][p]);
}

int main()
{
	int t,i,j,k,x,y;
	in>>n>>t;
	for (i=2;i<=n;i++)
	{
		in>>x;
		a[x].push_back(i);
	}
	dfs(1,0);
	for (i=v[0];i;i--)
	{
		rmq[i][0]=v[i];
		for (j=k=1;i+(k<<1)<=v[0]+1;j++,k<<=1)
			rmq[i][j]=best(rmq[i][j-1],rmq[i+k][j-1]);
	}
	for (i=v[0];i;i--)
		poz[v[i]]=i;
	level[0]=1<<30;
	while (t--)
	{
		in>>x>>y;x=poz[x];y=poz[y];
		if (x>y)
		{
			int aux=x;
			x=y;
			y=aux;
		}
		out<<query(x,y-x+1)<<"\n";
	}
	return 0;
}