题目描述
#10135. 「一本通 4.4 练习 2」祖孙询问 - 题目 - LibreOJ (loj.ac) 已知一棵 个节点的有根树。有 个询问，每个询问给出了一对节点的编号 和 ，询问 与 的祖孙关系。
输入格式
输入第一行包括一个整数 表示节点个数；
接下来 行每行一对整数对 和 表示 和 之间有连边。如果 是 ，那么 就是树的根；
第 行是一个整数 表示询问个数；
接下来 行，每行两个正整数 和 ，表示一个询问。
输出格式
对于每一个询问，若 是 的祖先则输出 ，若 是 的祖先则输出 ，否则输出 。
样例
输入
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数据范围与提示
对于 的数据，；
对于 的数据，，每个节点的编号都不超过 。
思路
从两个点找到他们的最近公共祖先, 判断是否为另一个点, 若是则输出1/2, 不是则输出0。
寻找最近公共祖先朴素做法是, 先从x点网上搜到根节点, 并标记走过的点, 再从y节点向上搜, 当第一次碰到x标记过的节点时, 该节点就是x和y的最近公共祖先。时间复杂度为 。
还有一种做法叫做倍增, 利用二进制优化向上跳的过程。先处理出每个点的深度, 接着处理每个点向上跳 步时的点编号 。
当要查询时, 先找深的点开始往上跳, 直到的深度相等, 对于 的深度差 , 作为整数可以由二进制凑成, 当前点能跳的为 , 从高到低枚举, 如果符合 , 则说明 此时是深度差的二进制最高位, 直接跳过去。 类似于 操作将其减去。 这样就可以以 的复杂度逼近。深度相同后, 若两个点并不相等 时, 将两个点一起往上跳。直到相等后就是他们的公共祖先。
时间复杂度为： 预处理采用BFS 查询
预处理 时可以采用类似DP的递推形式, 。即跳 时可以用跳两次 得出。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 4e4 + 10, M = 2 * N;
int h[N], ne[M], e[M], idx;
int depth[N];
int f[N][16];
int n, m;
int q[N];
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
void bfs(int root)
{
memset(depth, 0x3f, sizeof depth);
int hh = 0, tt = 0;
q[0] = root;
depth[root] = 1, depth[0] = 0;
while (hh <= tt)
{
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (depth[j] > depth[t] + 1)
{
depth[j] = depth[t] + 1;
q[++tt] = j;
f[j][0] = t;
for (int k = 1; k < 16; k++)
f[j][k] = f[f[j][k - 1]][k - 1];
}
}
}
}
int lca(int a, int b)
{
if (depth[a] < depth[b])
swap(a, b);
for (int k = 15; k >= 0; k--)
if (depth[f[a][k]] >= depth[b])
a = f[a][k];
if (a == b)
return a;
for (int k = 15; k >= 0; k--)
if (f[a][k] != f[b][k])
a = f[a][k], b = f[b][k];
return f[a][0];
}
int main()
{
int root = -1;
memset(h, -1, sizeof h);
cin >> n;
while (n--)
{
int a, b;
cin >> a >> b;
if (b == -1)
root = a;
else
add(a, b), add(b, a);
}
cin >> m;
bfs(root);
while (m--)
{
int a, b;
cin >> a >> b;
int p = lca(a, b);
if (p == a)
cout << 1 << endl;
else if (p == b)
cout << 2 << endl;
else
cout << 0 << endl;
}
return 0;
}