1. 看到"每个行星只有一条出边"，你就该知道这是基环树
Planets Queries II 这道题，我在图论题单里碰到过好几次了。题面本身并不复杂：宇宙中有 n 个行星，每个行星恰好发射一条单向航线到另一个行星，然后给你 q 次询问，每次问从行星 a 出发，能不能到达行星 b，如果能的话最少要飞几段航线。
第一次读题的人，脑子里第一个冒出来的多半是"最短路径"四个字。但只要你再仔细看一眼"每个行星恰好发射一条单向航线"，就会意识到整张图压根不是普通的有向图，而是一个典型的函数图（functional graph）：每个节点只有一个后继。从一个点出发，路径唯一，一直走下去迟早会绕进一个环里。
为什么这个条件这么重要？因为"路径唯一"意味着任意两点之间如果可达，路径只有一条，不存在什么"多条路径选最短"的问题。更妙的是，整张图一定是由若干棵"内向树"加一个环组成的——每一棵树的根都长在环上，树上的边全部指向环的方向。我在第 2 节会把这条性质讲透。
很多人在第一道 Planets Queries 上 AC 得很轻松，因为第一题只问"从 a 走 k 步能到哪"，用一个倍增表（binary lifting）把跳跃步数按二进制拆开，O(log n) 就能答完。到了第二题，问题从"给定步数求终点"变成"给定终点求步数"，同时还多了一个前置判断：a 到 b 到底可不可达。这一步直接把你从"会跳表"逼到"懂 LCA 思想"的程度。我当年也是卡在这里：第一题用模板改改就过，第二题一上来写了个 BFS，交了超时，又试了 Floyd，发现想都不用想，最后老老实实把找环、深度、入口、倍增表、祖先判定连在一起才理清楚。
如果你也卡在类似的位置，这篇文章应该能帮你把整条链路捋顺。我会把每一步的原理、代码、易错点全部过一遍，最后的代码可以直接拿去对拍。
2. 函数图的本质：一切都是为了那个环
2.1 先建立图模型
先把题面翻译成计算机能处理的模型。n 个点，每个点 i 有一条出边 to[i]，表示从 i 出发可以飞到 to[i]。这就有：
- 每个节点的出度为 1，入度随意。
- 顺着任意节点走，路径唯一。
- 图由若干个弱连通分量组成，每个分量里恰好有一个有向环，环上挂着若干棵内向树。
为了后面讨论方便，把"深度"定义成从节点出发，沿着出边走到环上节点的步数，环上节点深度记 0。把"入口"定义成从节点出发第一次碰到的那个环节点。这样每个非环节点往前走 depth 步，就会站在自己的入口上；再继续走，就只能在环上转圈了。
这里有个值得停下来品一品的性质：一旦从树上进入环，就永远不可能再回到任何树节点。原因很简单，每个节点只有一个出边，环上的节点把唯一的出边用来指向环内的下一个节点，根本没有分支去指向环外。所以"a 能否到 b"的判断，完全可以基于"b 在不在 a 的入口路径上，或者在不在环上"这两个条件来分类讨论。
2.2 三种情况，一个判定表
把查询归纳一下，任意 a、b 之间只会落在这三种情况里：
- a 和 b 不在同一个环上。也就是说它们属于不同的弱连通分量，航线根本连不到一起，直接输出 -1。
- b 在环上。a 必然能走到自己的入口，入口在环上，而单向环上任意一点出发都能绕一圈访问环上所有节点，所以 b 必可达。步数 = depth[a] + 环上从入口到 b 的有向距离。
- b 不在环上。那 b 必须位于 a 通往入口的那条链上，也就是 b 是 a 的祖先。如果 b 不在 a 的祖先链上，a 一旦走过 b 所在的位置就再也不会回头，所以不可达。步数 = depth[a] - depth[b]。
这张表就是整道题的灵魂。你可能会发现，第 2 种情况里如果入口到 b 的环上距离为 0，代表入口就是 b，那答案正好是 depth[a]，对应路径就是 a 沿树链一路走到入口，逻辑完全自洽。
2.3 别被"最短路"三个字带偏
普通图上的最短路算法，到这里全是多余的。BFS 单次要 O(n)，q 次询问就是 O(nq)，n 和 q 都是 2e5 的时候直接 4e10，肯定超时。Floyd 更不用提，O(n^3) 光预处理就已经不可能了。Dijkstra 是给"多条边、带权、需要选路径"的场景用的，这里从一个点到另一个点如果可达，路径唯一，没有任何决策过程。
所以这题真正需要的，不是一个"最短路径算法"，而是一个"快速跳转工具"。工具的名字叫倍增表，也就是二进制跳跃表。它能让你从一个点出发，按 2 的幂次步数跳着走，而不是一步一步走。下一节仔细说。
3. 倍增表与 LCA：这题的核心工具
3.1 up 数组怎么建
up[i][k] 表示从 i 出发沿着出边走 2^k 步之后到达的节点。构建方式非常机械：
- up[i][0] = to[i]，也就是走一步到的节点。
- 对 k 从 1 到 LOG-1：up[i][k] = up[ up[i][k-1] ][k-1]。
第二条递推式的意义是"跳 2^(k-1) 步先到中间节点，再从中间节点跳 2^(k-1) 步"。只要建好这个表，给你任意 step，你都可以把 step 拆成二进制，逐位判断是否需要跳对应档位，总跳数不超过 LOG 次。
我习惯把 LOG 设成 20 或者 21。n 最多 2e5，2^18 是 262144，所以 18 就够用了，但多留两档能避免某些边界数据把表给顶穿。数组开 MAXN 乘 LOG，内存也就 400 万个 int，大约 16MB，很轻松。
3.2 祖先判定：LCA 的降级用法
有了 up 表，怎么判断"b 是不是 a 的祖先"？标准 LCA 里有一个经典结论：如果 u 是 v 的祖先，那么从 v 往上跳到深度等于 u 的位置，跳到的节点就是 u。放在这题里完全一样，只不过方向换成了"a 往上跳"。
判断之前先看深度：如果 depth[b] > depth[a]，说明 b 比 a 更深，那 b 不可能是 a 的祖先，直接输出 -1。如果 depth[b] <= depth[a]，把 a 向上跳 depth[a] - depth[b] 步，看落点是不是 b。如果是，说明 b 在 a 的祖先链上；如果不是，说明 a 和 b 虽然在同一个连通分量里，但 b 在另一条树枝上，不可达。
这里有一个很容易被忽略的角落：如果 depth[a] == depth[b] 但 a 不等于 b，那么 need = 0，a 往上跳 0 步还是自己，不等于 b，自然输出 -1。这个结果其实是正确的，因为同一深度的节点不可能互相成为祖先，除非它们本来就是同一个点。所以代码里不需要为这种情况单独写分支。
为什么不能用传统的 DFS 时间戳来判断祖先？因为基环树不是严格意义上的树。环上的节点互为"祖先"关系，但在看时间戳时，环上节点的进出关系非常绕，处理起来反而麻烦。直接用深度差加倍增上跳，干净利落。
3.3 环上距离：关键公式与取模的坑
最后一个拼图是环上距离。假设环长 len，入口在环上的位置是 posEntry，目标 b 在环上的位置 posB。入口沿环走到 b 需要的步数是：
(posB - posEntry + len) % len
这个公式看起来人畜无害，实际写代码时有三个细节要小心：
- 顺序不能反。目标减入口，不是入口减目标。单向环上从入口到目标的方向是固定的，反了答案就完全错了。
- 一定加 len 再取模。posB - posEntry 可能是负数，直接对负数取模，C++ 会给你一个负数结果，然后整个答案就乱了。
- 环上节点的 pos 从 0 开始编号，还是从 1 开始，要全代码统一。我习惯从 0 编号，这样公式里 pos 值能直接参与运算。
举个小例子：环长 5，入口在位置 3，目标在位置 0。posB - posEntry = 0 - 3 = -3，加上 len 变成 2，意味着从位置 3 出发要顺时针走 2 步到位置 0。如果你写的是 (-3) % 5，在 C++ 里结果是 -3，然后 depth 加上一个负数，答案直接变成负数，绝对错。
还有一个容易忽略的情况：如果 a 自己就在环上，那么 depth[a] = 0，入口就是 a 自己。此时环上距离公式变成 (posB - posA + len) % len，这其实就是两个环节点的有向距离。很多人在这个角落会怀疑公式是不是漏了什么东西，但其实只要代入就会发现，它跟直观完全一致。这个性质也意味着，环上的每个点都是自己那棵树的入口，查询代码完全不需要为环上节点单独写分支。
4. 完整实现：找环、算深度、建表、查询
4.1 第一步：拓扑排序把环抠出来
找环的方法很多，我推荐用拓扑排序，因为它写起来短，而且能顺带完成"区分环上节点和非环节点"这件事。
做法：统计每个点的入度，把入度为 0 的点全丢进队列。每次取出队首 u，把 to[u] 的入度减 1；如果变 0 就继续入队。最后，入度仍然大于 0 的点，必然在环上。原理很简单：环上的每个节点都有一个来自环内的入度，这个入度永远不会被减到 0，所以它们不会被队列弹出。
这一步做完，用 onCycle[i] = (indeg[i] > 0) 把环上节点永久标记下来。注意，后续代码里千万不要再修改 indeg 数组，否则这一步的判断就废了。
4.2 第二步：给环编号并记录坐标
接下来遍历每个环节点，如果它还没有环编号，就顺着出边往下走，一边走一边分配环编号，同时记录每个节点在环内的坐标和这个环的长度。我的写法是：
while (cycId[cur] == 0) { cycId[cur] = cid; posInCyc[cur] = (int)cyclesNodes[cid].size(); cyclesNodes[cid].push_back(cur); cur = toArr[cur]; } cycLen[cid] = (int)cyclesNodes[cid].size();这个循环有一个很隐蔽的优点：因为节点一旦被标记立即退出循环，不会出现重复走环的死循环。如果你用 while (cur != start) 这种写法，万一中途走到一个已经被标记过的节点，就可能绕不回来，代码直接卡死。
4.3 第三步：反向 BFS 求深度和入口
现在深度还是未知数，但环上的点深度已经确定是 0。怎么把深度推广到树上所有节点？答案是反向 BFS。先构造一个反向图 revGraph[v]，里面存所有出边指向 v 的节点。把环上所有节点入队，深度设为 0，入口设为自己，然后一层层向外扩展：
- 从 u 扩展到 v = revGraph[u] 里的一个节点；
- 如果 v 是环上的节点，跳过（环上已经初始化过了）；
- 否则 depth[v] = depth[u] + 1，entry[v] = entry[u]，继续入队。
为什么必须反向 BFS？因为从环向外看，每个树节点的深度正好等于它到环的距离，入口正好等于它向上追到的第一个环节点。反向 BFS 天然就是树形扩散，逻辑非常顺。正向 DFS 也不是不行，但你要自己处理递归栈和重复访问，代码会啰嗦不少。
4.4 第四步：构建倍增表
倍增表的构建没有任何前置依赖，up[i][0] = toArr[i] 就能直接开建。需要注意循环顺序：外层一定是 k，内层才是 i。因为 up[i][k] 需要用到 up[i][k-1] 那一整列的数据，如果你把 i 放外层，某一层的值还没算完就拿来算下一层，结果就是一堆随机值。
4.5 第五步：查询逻辑分层
查询部分我按下面的顺序写，每个分支之间没有重叠，逻辑不会乱：
- a == b，直接输出 0。别小看这个分支，漏了它，后面公式算出来可能是 len 而不是 0，答案会差很远。
- cycId[a] != cycId[b]，说明不连通，输出 -1。
- onCycle[b] 为真，说明 b 在环上，套环上有向距离公式，输出 depth[a] + 环上距离。
- 其余情况，b 不在环上。先判断 depth[b] 是否大于 depth[a]，是则 -1；否则把 a 向上跳 depth[a] - depth[b] 步，落点等于 b 就输出深度差，否则 -1。
这里有一个我想强调的细节：第 4 步是从 a 往上跳，不是从 b 往上跳。原因是我们的图只有出边、没有回边，你没法从 b 往下走。要验证"b 是不是 a 的祖先"，只能把 a 往祖先方向拉，拉到 b 的高度再看落点是不是 b。方向反了，代码写起来会很别扭，而且极易错。
5. 可直接运行的 C++ 实现
下面是完整代码。为节省篇幅，我采用的是 C++17 常规写法，注释尽量放在关键位置。你直接用它对拍即可。
#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; const int LOG = 20; int n, q; int toArr[MAXN]; int indeg[MAXN]; bool onCyc[MAXN]; int cycId[MAXN]; int posInCyc[MAXN]; int cycLen[MAXN]; vector<int> cyclesNodes[MAXN]; int depthArr[MAXN]; int entryArr[MAXN]; int up[MAXN][LOG]; vector<int> revGraph[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> toArr[i]; indeg[toArr[i]]++; revGraph[toArr[i]].push_back(i); } // 拓扑剔除非环节点 queue<int> que; for (int i = 1; i <= n; i++) { if (indeg[i] == 0) que.push(i); } while (!que.empty()) { int u = que.front(); que.pop(); int v = toArr[u]; if (--indeg[v] == 0) que.push(v); } for (int i = 1; i <= n; i++) { onCyc[i] = (indeg[i] > 0); } // 给每个环节点分配环编号和环内坐标 int cid = 0; for (int i = 1; i <= n; i++) { if (onCyc[i] && cycId[i] == 0) { cid++; int cur = i; while (cycId[cur] == 0) { cycId[cur] = cid; posInCyc[cur] = (int)cyclesNodes[cid].size(); cyclesNodes[cid].push_back(cur); cur = toArr[cur]; } cycLen[cid] = (int)cyclesNodes[cid].size(); } } // 初始化环上节点：深度0，入口为自身 for (int i = 1; i <= n; i++) { if (onCyc[i]) { depthArr[i] = 0; entryArr[i] = i; } else { depthArr[i] = -1; } } // 反向BFS填充树上节点的深度与入口 for (int i = 1; i <= n; i++) { if (onCyc[i]) que.push(i); } while (!que.empty()) { int u = que.front(); que.pop(); for (int v : revGraph[u]) { if (onCyc[v]) continue; depthArr[v] = depthArr[u] + 1; entryArr[v] = entryArr[u]; que.push(v); } } // 构建倍增表 for (int i = 1; i <= n; i++) up[i][0] = toArr[i]; for (int k = 1; k < LOG; k++) { for (int i = 1; i <= n; i++) { up[i][k] = up[ up[i][k - 1] ][k - 1]; } } while (q--) { int a, b; cin >> a >> b; if (a == b) { cout << 0 << '\n'; continue; } if (cycId[a] != cycId[b]) { cout << -1 << '\n'; continue; } if (onCyc[b]) { int entry = entryArr[a]; int len = cycLen[cycId[a]]; int distOnCycle = (posInCyc[b] - posInCyc[entry] + len) % len; cout << depthArr[a] + distOnCycle << '\n'; } else { if (depthArr[b] > depthArr[a]) { cout << -1 << '\n'; continue; } int need = depthArr[a] - depthArr[b]; int cur = a; for (int k = 0; k < LOG; k++) { if (need & (1 << k)) { cur = up[cur][k]; } } if (cur == b) { cout << depthArr[a] - depthArr[b] << '\n'; } else { cout << -1 << '\n'; } } } return 0; }如果你用的不是 C++，而是 Python，那么实现思路完全一样，只是有两点要特别留意：一是递归深度，找环和反向 BFS 过程中不要用深递归，建议全部用 while 和队列迭代解决；二是数组维度，Python 里做 up 表时记得把内层长度设为 LOG，不然索引越界会找半天。
6. 手算样例：把查询流程完整走一遍
6.1 一个六节点样例的构建
为了把这些概念落到地面上，我构造一个小数据来手动走一遍。
n = 6，航线：1 -> 2，2 -> 3，3 -> 4，4 -> 2，5 -> 4，6 -> 5。这个图里，2 -> 3 -> 4 -> 2 是一个长度为 3 的环，1 挂在 2 上，5 和 6 挂在 4 所在的树上，6 再挂在 5 上。
先算深度和入口。环节点 2、3、4 的深度都是 0，入口是自己。1 指向 2，所以 depth[1] = 1，entry[1] = 2。4 指向 5，所以 depth[5] = 1，entry[5] = 4。5 指向 6，所以 depth[6] = 2，entry[6] = 4。
6.2 四组查询的完整推导
查询 (6, 3)。6 的深度是 2，入口是 4。b=3 在环上，环长 3，posInCyc[3] = 1，posInCyc[4] = 2。环上距离 = (1 - 2 + 3) % 3 = 2，总答案 = 2 + 2 = 4。实际路径是 6 -> 5 -> 4 -> 2 -> 3，四步，正确。
查询 (1, 5)。depth[1] = 1，depth[5] = 1。b 不在环上，depth 相等，需要把 1 向上跳 0 步，落点是 1，不等于 5，输出 -1。实际路径 1 -> 2 -> 3 -> 4 -> 2，永远到不了 5，正确。
查询 (2, 4)。b 在环上，a 也在环上，depth[2] = 0，entry[2] = 2。posInCyc[4] = 2，posInCyc[2] = 0，环上距离 = (2 - 0 + 3) % 3 = 2，答案是 2。路径 2 -> 3 -> 4，两步，正确。
查询 (4, 2)。b 在环上，posInCyc[2] = 0，posInCyc[4] = 2，环上距离 = (0 - 2 + 3) % 3 = 1，答案是 1。路径 4 -> 2，一步，正确。
这个样例最大的价值，是让你直观看到有向环上的距离不满足对称性：从 2 到 4 是两步，从 4 到 2 却只有一步。所以公式里 pos 的顺序一定是"终点减起点"，你想从代码层面验证方向对不对，可以专门构造一个三个节点的环反复测试。
7. 复杂度分析：为什么这套方案能跑进时限
7.1 时间复杂度到底是多少
时间复杂度分四块：拓扑找环 O(n)、反向 BFS O(n)、倍增表预处理 O(n log n)、每次查询 O(log n)。总的复杂度是 O((n + q) log n)。n 和 q 都取 2e5 的时候，log n 大约是 18，总操作量大概在几百万到一千万级别，对 C++ 来说是零压力。
空间上，主要开销是 up 表：MAXN 乘 LOG，2e5 乘 20，400 万个 int，约 16MB。加上其他数组，总内存也就二三十 MB，同样很宽松。
7.2 LOG 怎么选，常数怎么优化
这里有一个优化小技巧：查询循环里的跳跃，可以用 for k 从 LOG-1 往下扫，也可以从 0 往上扫。两种写法在二进制拆分时效果一样，但从 0 往上扫更贴合 need 的二进制表示，而且不容易出现"跳过头"的问题。我自己习惯从 0 往上扫，理由是 need 最多只有 LOG 位，逐位看就好，不用考虑大端小端。
如果遇到极端数据，比如环非常长、树非常深，depth 可能达到 1e5 量级，up 表依然扛得住。只要 LOG 取到 18 以上就不会跳不到。我见过有人把 LOG 设成 15，结果在 n=2e5 的链上直接错，原因就是 depth 超过了 2^15，跳不到目标节点。这种坑在测小数据时完全看不出来，所以 LOG 宁可多开一两档，不要贪省。
8. 解题过程中的常见错误与排查实录
8.1 答案差一个长度单位，先检查取模方向
环上有向距离写反，是最常见的错误。判断方法很简单：找一个长度大于 1 的环，跑两个方向相反的查询，答案应该不一样。如果你发现正反查询答案一样，多半是公式写成了 (abs(posB - posEntry)) % len，这会把有向距离变成无向距离，样例小数据可能看不出来，跑到长环数据就全错。
8.2 找环死循环，多半是循环退出条件写错
我见过不少人用 while (cur != start) 找环，在环比较大的时候确实能过，但一旦当前环里有一个节点已经被之前的环标记过，cur 可能永远走不到 start，于是死循环。比较稳的写法是 while (cycId[cur] == 0)，一边走一边标记，标记过就停。这样不管之前有没有遍历过，循环一定会在有限步内结束。
8.3 深度 -1 和 0 的混淆
初始化时，非环节点的 depth 我设的是 -1，而不是 0。如果设成 0，反向 BFS 里你会区分不了"这个点已经算过深度 0"和"这个点还没算过"，然后环上节点和非环节点的深度全部乱套。设成 -1 以后，每次扩展开来都必然满足 depth[v] = depth[u] + 1，而 u 的深度一定大于等于 0，所以 v 的深度一定大于等于 1，不会和环节点的 0 冲突。
8.4 忘记特判 a == b
a 和 b 相同的时候，按公式走，b 在环上分支可能给你一个正数，比如 a 是环节点，b 是同一节点，环上距离算出来可能是 len 而不是 0。这会导致结果比正确答案大。所以查询第一步就先判断 a == b 直接输出 0，简单省事。
8.5 对拍：验证一切不确定性的终极手段
如果你对自己代码的正确性没有十足把握，我强烈建议写一个暴力版来对拍。暴力版每次查询用队列从 a 开始 BFS，记录步数，能在步数上限内找到 b 就输出，否则 -1。然后随机生成小图，跑几千组数据。我每次写带环的题都会对拍，因为手算样例的覆盖能力非常有限，很多边界情况只有随机数据能触到。
9. 这类题的通用套路：从 Planets Queries II 出发
9.1 换皮之后，核心思维还是那一套
刷题的意义不只在于 AC，更在于把背后的模型吃透。Planets Queries II 用到的"函数图上做路径查询"模型，在很多竞赛题里都会改头换面出现。
比如有的题会换成"每个节点只有一条入边"的内向树模型，方向反了，但找环、倍增、深度这套思维完全不变；有的题会问"从 a 出发恰好走 k 步到达的点"，这时候倍增表是核心，查询部分只是跳表而已；还有的题会和 DP 结合，比如环上每个节点带权，问绕环若干圈后的最优收益——这类题通常会先找环，然后用环形 DP 或者环上倍增处理。
9.2 我自己的固定套路：四条标准动作
我自己的做题习惯是，看到"每个节点只有一个后继/前驱"这类描述，立刻在脑子里拉起四条标准动作：拓扑找环、反向求深度、倍增建表、环上按周期处理。这套动作练熟了，基环树题在你眼里就不再是"不知道从哪下手"，而是"模板拼装"。
Planets Queries II 恰好把这四条动作完整串了一遍，所以经常会作为基环树综合题出现在图论题单里。刷明白这一道，后面再遇到类似的题，你对它的掌控感会强很多。
最后分享一个小习惯：写这类题前，我会先把 depth、entry、posInCyc 这几个数组的语义用注释写在代码最上面，再开始动手。每个数组是什么含义、存的是什么值、用在哪个公式里，都写清楚之后，写查询分支时就能做到逐行对上逻辑，而不是边写边猜。这个习惯帮我省下了非常多调试时间。
