题解：AcWing 1172 祖孙询问

【题目来源】

AcWing：1172 祖孙询问 - AcWing题库

【题目描述】

给定一棵包含 \(n\) 个节点的有根无向树，节点编号互不相同，但不一定是 \(1\sim 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\)。

【输入样例】

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. 问题分析：给定一棵包含 \(n\) 个节点的有根无向树，节点编号互不相同，有 \(m\) 个询问，每个询问给出节点对 \((x, y)\)，需要判断 \(x\) 与 \(y\) 的祖孙关系。这是一个最近公共祖先（LCA）问题，通过判断 LCA 与询问节点的关系来确定祖孙关系。

2. 算法选择：

   • 倍增法求 LCA：预处理每个节点向上走 \(2^k\) 步到达的祖先节点，支持 \(O(\log n)\) 时间复杂度的 LCA 查询
   • BFS 预处理：从根节点出发进行 BFS，计算每个节点的深度 \(dep[]\) 和倍增祖先数组 \(fa[][]\)
   • 祖孙关系判定：
     • 若 \(LCA(x, y) = x\)，则 \(x\) 是 \(y\) 的祖先，输出 \(1\)
     • 若 \(LCA(x, y) = y\)，则 \(y\) 是 \(x\) 的祖先，输出 \(2\)
     • 否则 \(x\) 和 \(y\) 无祖孙关系，输出 \(0\)

3. 关键步骤：

   • 建树与找根：
     • 读入 \(n\) 条边 \((a, b)\)，使用邻接表存储树
     • 若 \(b = -1\)，则 \(a\) 为根节点
   • BFS 预处理（从根节点开始）：
     • 初始化深度数组 \(dep[]\) 为无穷大，\(dep[root] = 1\)
     • 队列中加入根节点，进行 BFS 遍历
     • 对于每个节点 \(j\)，记录 $fa[j][0] = $ 父节点（向上走 \(2^0 = 1\) 步）
     • 倍增预处理：对于 \(k\) 从 \(1\) 到 \(D\)（\(D = 15\)，因为 \(2^{15} > 40000\)）：
       • \(fa[j][k] = fa[fa[j][k-1]][k-1]\)（\(j\) 向上走 \(2^k\) 步等于先走 \(2^{k-1}\) 步再走 \(2^{k-1}\) 步）
   • LCA 查询（节点 \(x\) 和 \(y\)）：
     • 深度对齐：若 \(dep[x] < dep[y]\)，交换 \(x\) 和 \(y\)，确保 \(x\) 深度较大
     • 提升 \(x\)：从 \(k = D\) 到 \(0\)，若 \(dep[fa[x][k]] \geq dep[y]\)，则 \(x = fa[x][k]\)（将 \(x\) 提升到与 \(y\) 同一深度）
     • 判断祖先：若 \(x = y\)，返回 \(x\)（\(y\) 是 \(x\) 的祖先）
     • 同步提升：从 \(k = D\) 到 \(0\)，若 \(fa[x][k] \neq fa[y][k]\)，则 \(x = fa[x][k]\)，\(y = fa[y][k]\)（同时向上跳，直到 LCA 的下一层）
     • 返回 \(fa[x][0]\)（LCA）
   • 回答询问：对每个询问 \((a, b)\)，计算 \(p = LCA(a, b)\)，根据 \(p\) 与 \(a, b\) 的关系输出 \(1, 2\) 或 \(0\)

4. 时间/空间复杂度：

   • 预处理时间复杂度：\(O(n \log n)\)，BFS \(O(n)\)，倍增预处理每个节点 \(O(\log n)\)
   • 单次 LCA 查询时间复杂度：\(O(\log n)\)，每次查询最多跳 \(\log n\) 次
   • 总时间复杂度：\(O(n \log n + m \log n)\)
   • 空间复杂度：\(O(n \log n)\)，\(fa[][]\) 数组需要 \(n \times \log n\) 的空间

5. 倍增法 LCA 的核心思想：

   • 二进制拆分：将"向上走 \(k\) 步"拆分为二进制表示，如走 \(13\) 步 = 走 \(8 + 4 + 1\) 步，对应 \(2^3 + 2^2 + 2^0\)
   • 倍增预处理：\(fa[x][k]\) 表示节点 \(x\) 向上走 \(2^k\) 步到达的祖先，通过递推 \(fa[x][k] = fa[fa[x][k-1]][k-1]\) 快速计算
   • 深度对齐：先将较深的节点提升到与较浅节点同一深度，保证两节点在同一层进行比较
   • 同步跳跃：从大到小尝试跳跃，若跳跃后两节点不同，则同时向上跳，直到 LCA 的下一层
   • 适用场景：静态树（树结构不变）、多次查询 LCA 的问题
   • 预处理一次，查询多次，适合询问次数较多的场景

【解题思路】

【算法标签】

最近公共祖先

【代码详解】

#include <bits/stdc++.h>  // 包含所有标准库头文件
using namespace std;const int N = 40005;  // 定义常量：N为节点数量上限
const int D = 16;  // 定义常量：D为最大深度（2^15足够覆盖大多数树的深度）
int n, m;  // n：节点数量；m：询问数量
vector<int> h[N];  // 邻接表存储树
int dep[N];  // dep[i]：节点i的深度
int fa[N][D];  // fa[x][i]：节点x向上走2^i步到达的节点
queue<int> q;  // 队列，用于BFS// BFS函数，预处理每个节点的深度和fa数组
void bfs(int root)
{memset(dep, 0x3f, sizeof(dep));  // 初始化深度为无穷大dep[0] = 0, dep[root] = 1;  // 虚拟节点0的深度为0，根节点的深度为1q.push(root);  // 将根节点加入队列while (!q.empty()) {  // 当队列不为空时int t = q.front();  // 取出队首节点q.pop();// 遍历t的所有邻接节点for (int i = 0; i < h[t].size(); i++) {int j = h[t][i];  // 邻接节点jif (dep[j] > dep[t] + 1) {  // 如果j的深度未被更新dep[j] = dep[t] + 1;  // 更新j的深度q.push(j);  // 将j加入队列fa[j][0] = t;  // j向上走2^0=1步到达t// 递推计算fa[j][k]for (int k = 1; k <= 15; k++) {fa[j][k] = fa[fa[j][k - 1]][k - 1];  // j向上走2^k等于j向上走2^(k-1)后再走2^(k-1)步}}}}
}// LCA函数，计算节点x和节点y的最近公共祖先
int lca(int x, int y)
{if (dep[x] < dep[y]) swap(x, y);  // 保证x为深度较大的节点// 步骤1：将x和y的深度调整一致for (int k = 15; k >= 0; k--) {if (dep[fa[x][k]] >= dep[y]) {  // 如果x向上走2^k步后深度仍大于等于yx = fa[x][k];  // x向上走2^k步}}if (x == y) return x;  // 如果x和y相等，说明x就是LCA// 步骤2：x和y同时向上跳，跳到LCA的下一层for (int k = 15; k >= 0; k--) {if (fa[x][k] != fa[y][k]) {  // 如果x和y向上走2^k步后不相等x = fa[x][k];  // x向上走2^k步y = fa[y][k];  // y向上走2^k步}}return fa[x][0];  // 返回x或y的父节点，即LCA
}int main()
{cin >> n;  // 输入节点数量nint root = 0;  // 根节点初始化为0// 输入树的边for (int i = 1; i <= n; i++) {int a, b;cin >> a >> b;  // 输入边的两个节点a和bif (b == -1) root = a;  // 如果b为-1，说明a是根节点else {h[a].push_back(b);  // 添加边a->bh[b].push_back(a);  // 添加边b->a（无向图）}}bfs(root);  // 预处理fa数组和dep数组cin >> m;  // 输入询问数量mwhile (m--) {int a, b;cin >> a >> b;  // 输入询问的两个节点a和bint p = lca(a, b);  // 计算a和b的LCAif (p == a) puts("1");  // 如果LCA是a，输出1else if (p == b) puts("2");  // 如果LCA是b，输出2else puts("0");  // 否则输出0}return 0;  // 程序结束
}

【运行结果】

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