「4.4」祖孙询问

「4.4」祖孙询问

题目描述

已知一棵 n 个节点的有根树。有 m 个询问，每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。

输入格式

输入第一行包括一个整数 n 表示节点个数；
接下来 n 行每行一对整数对 a 和 b 表示 a 和 b 之间有连边。如果 b 是 -1，那么 a 就是树的根；
第 n+2 行是一个整数 m 表示询问个数；
接下来 m 行，每行两个正整数 x 和 y，表示一个询问。

输出格式

对于每一个询问，若 x 是 y 的祖先则输出 1，若 y 是 x 的祖先则输出 2，否则输出 0。

样例输入1

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

样例输出1

1
0
0
0
2

注释说明

对于 30% 的数据，1≤n,m≤10^3；
对于 100% 的数据，1≤n,m≤4×10^4，每个节点的编号都不超过 4×10^4。

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,pre[N],f[N][17],dep[N],k,lg[N];
struct node{
	int to,next;
}e[N*2];
void add(int u,int v){
	e[++k]=(node){v,pre[u]};
	pre[u]=k;
}
void dfs(int x,int fa){
	f[x][0]=fa;
	dep[x]=dep[fa]+1;
	for(int i=pre[x];i!=0;i=e[i].next){
		int to=e[i].to;
		if(to==fa)continue;
		dfs(to,x);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y])x=f[x][lg[dep[x]-dep[y]]];
	if(x==y)return x;
	for(int i=16;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			//printf("(%d,%d)",f[x][i],f[y][i]);
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
int main(){
	scanf("%d",&n);
	int rt,x,y;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x,&y);
		if(y==-1){
			rt=x;
			continue;
		}
		add(x,y);
		add(y,x);
	}
	dfs(rt,0);
	for(int i=2;i<=N;i++)lg[i]=lg[i/2]+1;
	for(int j=1;j<=16;j++){
		for(int i=1;i<=N;i++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
	int m;
	scanf("%d",&m);
	while(m--){
		scanf("%d%d",&x,&y);
		int lc=lca(x,y);
		//printf("%d\n",lc);
		if(lc==x)puts("1");
		else if(lc==y)puts("2");
		else puts("0");
	}
}
/*
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 234
234 17
233 13
233 15
233 19
*/