Cod sursa(job #369833)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 29 noiembrie 2009 17:25:26
Problema Lowest Common Ancestor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define file_in "lca.in"
#define file_out "lca.out"

#define Nmax 101000

int n,m;
vector<int> v[Nmax];
int h[Nmax];
int f[Nmax];
int l[Nmax];
int log[Nmax];
int r[21][Nmax/2];
int x,y,nr;

void dfs(int nod, int niv)
{
	vector<int> :: iterator it;
	
	h[++nr]=nod;
	l[nr]=niv;
	f[nod]=nr;
	
	for (it=v[nod].begin();it!=v[nod].end();++it)
	{
		dfs(*it, niv+1);
		h[++nr]=nod;
		l[nr]=niv;
	}
}

int lca(int x, int y)
{
	int rez;
	int a=f[x];
	int b=f[y];
	if (a>b) 
		swap(a,b);
	int lg=b-a+1;
	rez=r[log[lg]][a];
	
    if (l[rez]>l[r[log[lg]][a+lg-(1<<log[lg])]])
		rez=r[log[lg]][a+lg-(1<<log[lg])];
	return h[rez];
}

	
int main()
{
	int i,j,k;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
	for (i=2;i<=n;++i)
	{
		scanf("%d", &x);
		v[x].push_back(i);
	}
	
	dfs(1,0);
	
	/*for (i=1;i<=nr;++i)
		printf("%d ", h[i]);
	printf("\n");
	for (i=1;i<=nr;++i)
		 printf("%d ", l[i]);
	printf("\n");*/
    for (i=2;i<=nr;++i)
		 log[i]=log[i>>1]+1;
	for (i=1;i<=nr;++i)
		 r[0][i]=i;
	for (i=1;(1<<i)<nr;++i)
		 for (j=1;j<=nr-(1<<i);++j)
		 {
			 k=1<<(i-1);
			 r[i][j]=r[i-1][j];
			 if (l[r[i-1][j+k]]<l[r[i][j]])
				  r[i][j]=r[i-1][j+k];
		 }
		 
	while(m--)
	{
		scanf("%d %d", &x, &y);
		printf("%d\n", lca(x,y));
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}