https://old.ynoip.cn/problem/discuss?id=9197#

BALENCIAGA  •  3个月前


include<stdio.h>

include<string.h>

include

using namespace std; const int N=1e5+10; int t[N],f[N][30],head[N],ne[N],to[N],h[N]; int n,m,cnt,rt; void add(int x,int y) {

to[cnt]=y;
ne[cnt]=head[x];
head[x]=cnt++;

} void dfs(int x,int fa) {

h[x]=h[fa]+1;//儿子的深度是父亲的深度+1
f[x][0]=fa;//x的直接祖先是fa
for(int i=1; (1<<i)<=h[x]; i++)
	f[x][i]=f[f[x][i-1]][i-1];//RMQ原理,f的2^i祖先等于f的2^(i-1)祖先的2^(i-1)祖先
for(int i=head[x]; ~i; i=ne[i])//
{
	if(to[i]==fa)
		continue;
//	f[to[i]][0]=x;
	dfs(to[i],x);
}

} int lca(int x,int y) {

if(h[x]<h[y]) swap(x,y);//使x是大高度
for(int i=20;i>=0;i--)//把x和y变为同一高度
{
	if(h[f[x][i]]>=h[y])
	x=f[x][i];
	if(x==y)//如果x==y,说明x是祖先
	return x;
}
for(int i=20; i>=0; i--)//x,y一起向上跳,直到重合的下一个深度
	if(f[x][i]!=f[y][i])
		x=f[x][i],y=f[y][i];
return f[x][0];//此时上一深度,即为共同祖先

} int main() {

int a,b,i,j,k;
scanf("%d",&n);
rt=0;
memset(head,-1,sizeof(head));
for(i=0; i<n; i++)
{
	scanf("%d%d",&a,&b);
	if(b==-1)
		rt=a;
	else
		add(a,b),
		    add(b,a);
}
f[rt][0]=rt;//
dfs(rt,-1);
/*for(i=1; i<=21; i++)
	lg[i]=lg[i-1]+(1<<lg[i-1]==i);*/
scanf("%d",&m);
while(m--)
{
	scanf("%d%d",&a,&b);
	int p=lca(a,b);
	if(p==a)
		printf("1\n");
	else if(p==b)
		printf("2\n");
	else
		printf("0\n");
}
return 0;

}


评论:

请先登录,才能进行评论