[蓝桥杯]版本分支

版本分支

题目描述

小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(branch)但是从未发生过合并(merge)。

现在这个项目的代码一共有 NN 个版本，编号 1 ~ NN，其中 1 号版本是最初的版本。

除了 1 号版本之外，其他版本的代码都恰好有一个直接的父版本；即这 NN 个版本形成了一棵以 1 为根的树形结构。

如下图就是一个可能的版本树：

1

/ \

2 3

\ / \

5 4 6

现在小明需要经常检查版本 xx 是不是版本 yy 的祖先版本。你能帮助小明吗？

输入描述

第一行包含两个整数 N,QN,Q，代表版本总数和查询总数。

以下 NN - 1 行，每行包含 2 个整数 uu 和 vv ，代表版本 uu 是版本 vv 的直接父版本。

再之后 QQ 行，每行包含 2 个整数 xx 和 yy ，代表询问版本 xx 是不是版本 yy 的祖先版本。

其中，1≤N≤105,1≤Q≤1051≤N≤105,1≤Q≤105。

输出描述

对于每个询问，输出 YES 或 NO 代表 xx 是否是 yy 的祖先。

输入输出样例

示例

输入

6 5
1 2
1 3
2 5
3 6
3 4
1 1
1 4
2 6
5 2
6 4

输出

YES
YES
NO
NO
NO

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Python3	3s	256M
Java	3s	256M
PyPy3	3s	256M
Go	1s	256M
JavaScript	1s	256M

总通过次数: 299  |  总提交次数: 537  |  通过率: 55.7%

难度: 困难   标签: 2018, 并查集, 国赛, 离线处理

算法思路：DFS序判断祖先关系

要高效判断节点 x 是否是节点 y 的祖先，核心思路是利用 ​​DFS 时间戳​​（DFS 序）的特性：

1. ​​DFS 遍历​​：从根节点开始深度优先搜索
2. ​​时间戳记录​​：
   • ​​入栈时间​​ in[u]：节点 u 第一次被访问的时间
   • ​​出栈时间​​ out[u]：节点 u 结束递归返回的时间
3. ​​祖先判定原理​​：
   x 是 y 的祖先当且仅当：
   in[x] ≤ in[y] 且 out[x] ≥ out[y]
   （即 y 的 DFS 区间完全包含在 x 的区间内）

https://oi-wiki.org/graph/images/dfs-5.svg
DFS 时间戳示意图（来源：OI Wiki）

---

完整 C++ 代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;const int MAXN = 100010;int main() {ios::sync_with_stdio(false);cin.tie(0);// 输入数据int N, Q;cin >> N >> Q;// 邻接表存储树vector<vector<int>> graph(N+1);for (int i = 0; i < N-1; ++i) {int u, v;cin >> u >> v;graph[u].push_back(v);  // u是v的直接父节点}// DFS序时间戳vector<int> in_time(N+1, 0);vector<int> out_time(N+1, 0);int timer = 0;// 非递归DFS（避免递归栈溢出）stack<pair<int, int>> st;  // {当前节点, 下一个孩子索引}st.push({1, 0});in_time[1] = timer++;while (!st.empty()) {int u = st.top().first;int& idx = st.top().second;if (idx < graph[u].size()) {int v = graph[u][idx++];in_time[v] = timer++;st.push({v, 0});  // 访问子节点} else {out_time[u] = timer++;st.pop();}}// 处理查询while (Q--) {int x, y;cin >> x >> y;// 祖先判定核心条件if (in_time[x] <= in_time[y] && out_time[x] >= out_time[y]) {cout << "YES\n";} else {cout << "NO\n";}}return 0;
}

算法步骤详解

1. ​​建树​​（邻接表存储）

   • 输入 N-1 条父子关系边
   • 构建父节点→子节点的有向图

2. ​​DFS 时间戳生成​​

   • 初始化：根节点 1 入栈
   • 循环处理：
     • 取出栈顶节点 u
     • 访问 u 的下一个未处理子节点 v
     • 记录 in_time[v] = 当前时间
     • v 入栈并重置其子节点索引
     • 当 u 的子节点处理完毕时，记录 out_time[u]

3. ​​查询处理​​

   • 对每个查询 (x, y)：
     • 检查 in_time[x] ≤ in_time[y]
     • 检查 out_time[x] ≥ out_time[y]
     • 同时满足 → YES，否则 NO

---

实例验证（题目样例）

​​输入​​：

6 5
1 2
1 3
2 5
3 6
3 4
1 1
1 4
2 6
5 2
6 4

​​DFS 时间戳生成过程​​：

节点	入栈时间	出栈时间	区间
1	0	11	[0, 11]
2	1	4	[1, 4]
5	2	3	[2, 3]
3	5	10	[5, 10]
6	6	7	[6, 7]
4	8	9	[8, 9]

​​查询验证​​：

1. (1,1)：[0,11] 包含 [0,11] → YES
2. (1,4)：[0,11] 包含 [8,9] → YES
3. (2,6)：[1,4] 不包含 [6,7] → NO
4. (5,2)：[2,3] 不包含 [1,4] → NO
5. (6,4)：[6,7] 不包含 [8,9] → NO

---

关键测试点

1. ​​边界情况​​：

   • 根节点自身（x=1, y=1）
   • 叶子节点查询（y 是叶子节点）
   • x=y 但非根节点

2. ​​极端数据​​：

   • 链状树（深度 10^5）
   • 菊花图（根节点直接连接 10^5 子节点）

3. ​​特殊关系​​：

   • x 是 y 的直接父亲
   • x 是 y 的间接祖先（隔多代）
   • x 和 y 在不同分支

---

优化建议

1. ​​时间效率优化​​：

   • 使用非递归 DFS（已实现）
   • 输入输出加速（ios::sync_with_stdio(false)）

2. ​​空间优化​​：

   • 使用 vector 替代静态数组
   • 时间戳数组可优化为两个 int 数组

3. ​​可扩展性改进​​：

   // 添加 LCA 查询支持（需额外预处理）
   vector<vector<int>> parent(MAXN, vector<int>(20));
   void preprocess_lca() {for (int i = 1; i <= N; ++i)parent[i][0] = fa[i];  // fa[i] 存储直接父节点for (int j = 1; j < 20; ++j)for (int i = 1; i <= N; ++i)parent[i][j] = parent[parent[i][j-1]][j-1];
   }

---

注意事项

1. ​​递归深度风险​​：

   • 必须使用非递归 DFS
   • 递归实现在 N=10^5 时必然栈溢出

2. ​​输入顺序敏感性​​：

   • 建图时确保父子关系方向正确
   • 时间戳不受遍历顺序影响判定结果

3. ​​时间戳唯一性​​：

   • 每个时间点必须全局唯一
   • 使用单调递增计数器实现