求最近公共祖先 用求深度加快速度.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

#define NMAX 100002

//求最近公共祖先 用求深度加快速度
long fa[NMAX];
long shendu[NMAX];
void init(long num)
{
	long i;
	for(i=1;i<=num;i++)
		shendu[i]=-1;
}

long getshendu(long now)
{	//求该点的深度
	if(fa[now]==0) return 1;
	//如果该点深度未求，转去求父亲的深度（这样顺带把父亲的深度也求了）
	else if(shendu[now]==-1) {shendu[now]=getshendu(fa[now])+1;return shendu[now];}
	else return shendu[now];//若已求得，直接返回
}

long cal(long a,long b)
{
	//只需求所要节点的深度即可
	getshendu(a);
	getshendu(b);
	//将两点调整到同一深度上
	while(shendu[a]<shendu[b]) b=fa[b];
	while(shendu[b]<shendu[a]) a=fa[a];
	while(a!=b)
	{	//同时向祖先推进，直到相遇
		a=fa[a];
		b=fa[b];
	}
	return a;
}

int main()
{
	long num,i,numa,a,b;
	scanf("%ld",&num);
	for(i=1;i<=num;i++)
		scanf("%ld",&fa[i]);
	init(num);
	scanf("%d",&numa);
	for(i=0;i<numa;i++)
	{
		scanf("%ld%ld",&a,&b);
		printf("%ld\n",cal(a,b));
	}
	return 0;
}