题目描述
给定一棵包含 n 个节点的有根无向树，节点编号互不相同，但不一定是 1∼n。
有 m 个询问，每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。
输入格式
输入第一行包括一个整数 表示节点个数；
接下来 n 行每行一对整数 a 和 b，表示 a 和 b 之间有一条无向边。如果 b 是 −1，那么 a 就是树的根；
第 n+2 行是一个整数 m 表示询问个数.
接下来 m 行，每行两个不同的正整数 x 和 y，表示一个询问。
输出格式
对于每一个询问，若 x 是 y 的祖先则输出 1，若 y 是 x 的祖先则输出 2，否则输出 0。
数据范围
1≤n,m≤4×104,
1≤每个节点的编号≤4×104
输入样例
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
0
0
0
2
题目分析
这是一道用倍增法求最近公共祖先的模板题。
倍增法：
O(nlogn+qlogn) 在线算法
-
我们需要的预处理出的数组：预处理O(nlogn)
fa[i][j] //表示从i节点开始，向上走2^j步所能到达的节点。
depth[i] //表示i节点的深度
-
求两点最近公共祖先的步骤：查询O(logn)
1）
先让两个节点跳到同一层.
2）
让两个节点同时往上跳，跳到它们最近公共祖先的下一层为止。此时的答案即为：fa[a或b][0].
代码如下
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define x first
#define y second
using namespace std;
const int N=4e4+5,INF=0x3f3f3f3f;
vector<int> h[N]; //存图
int depth[N],fa[N][16];
void bfs(int root) //bfs预处理出fa[][]和depth[]两个数组
{
memset(depth,0x3f,sizeof depth);
queue<int> q;
depth[0]=0; depth[root]=1; //设0号点为哨兵，其深度为0。root的深度为1
q.push(root); //将root加入队列
while(q.size())
{
int t=q.front();
q.pop();
for(int i=0;i<h[t].size();i++)
{
int j=h[t][i];
if(depth[j]>depth[t]+1) //如果j的深度大于其父节点t的深度+1
{
depth[j]=depth[t]+1; //则更新depth[j]
q.push(j);
fa[j][0]=t; //j节点向上跳2^0步是t
for(int k=1;k<=15;k++) //j节点向上跳2^k步 等于 j节点向上跳2^k-1步的节点再向上跳2^k-1步
fa[j][k]=fa[fa[j][k-1]][k-1];
}
}
}
}
int lca(int a,int b) //求a和b节点的最近公共祖先
{
if(depth[a]<depth[b]) swap(a,b); //保证a的深度大于等于b的深度
for(int k=15;k>=0;k--) //先让a节点跳到和b的同一层上
if(depth[fa[a][k]]>=depth[b])
a=fa[a][k];
if(a==b) return a; //如果此时a==b，说明b节点即为a，b的最近公共祖先
for(int k=15;k>=0;k--)
if(fa[a][k]!=fa[b][k]) //让a和b跳到两节点最近公共祖先的下一层
{
a=fa[a][k];
b=fa[b][k];
}
return fa[a][0]; //最近公共祖先即为a/b的父节点
}
int main()
{
int n,root;
scanf("%d",&n);
while(n--) //建图
{
int u,v;
scanf("%d %d",&u,&v);
if(v==-1) root=u; //记录根节点
else {
h[u].push_back(v);
h[v].push_back(u);
}
}
bfs(root);
scanf("%d",&n);
while(n--) //q组询问
{
int a,b;
scanf("%d %d",&a,&b);
int p=lca(a,b); //p为a和b的最近公共祖先
if(p==a) puts("1"); //p==a说明a节点是b节点的祖先
else if(p==b) puts("2");//p==b说明b节点是a节点的祖先
else puts("0");
}
return 0;
}