基环树路径查询：函数图、倍增表与LCA思想解析

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-1up[i][k] up[ up[i][k-1] ][k-1]。第二条递推式的意义是跳 2^(k-1) 步先到中间节点再从中间节点跳 2^(k-1) 步。只要建好这个表给你任意 step你都可以把 step 拆成二进制逐位判断是否需要跳对应档位总跳数不超过 LOG 次。我习惯把 LOG 设成 20 或者 21。n 最多 2e52^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 0a 往上跳 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] 1entry[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 实现下面是完整代码。为节省篇幅我采用的是 C17 常规写法注释尽量放在关键位置。你直接用它对拍即可。#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]; vectorint cyclesNodes[MAXN]; int depthArr[MAXN]; int entryArr[MAXN]; int up[MAXN][LOG]; vectorint 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); } // 拓扑剔除非环节点 queueint 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 - 22 - 33 - 44 - 25 - 46 - 5。这个图里2 - 3 - 4 - 2 是一个长度为 3 的环1 挂在 2 上5 和 6 挂在 4 所在的树上6 再挂在 5 上。先算深度和入口。环节点 2、3、4 的深度都是 0入口是自己。1 指向 2所以 depth[1] 1entry[1] 2。4 指向 5所以 depth[5] 1entry[5] 4。5 指向 6所以 depth[6] 2entry[6] 4。6.2 四组查询的完整推导查询 (6, 3)。6 的深度是 2入口是 4。b3 在环上环长 3posInCyc[3] 1posInCyc[4] 2。环上距离 (1 - 2 3) % 3 2总答案 2 2 4。实际路径是 6 - 5 - 4 - 2 - 3四步正确。查询 (1, 5)。depth[1] 1depth[5] 1。b 不在环上depth 相等需要把 1 向上跳 0 步落点是 1不等于 5输出 -1。实际路径 1 - 2 - 3 - 4 - 2永远到不了 5正确。查询 (2, 4)。b 在环上a 也在环上depth[2] 0entry[2] 2。posInCyc[4] 2posInCyc[2] 0环上距离 (2 - 0 3) % 3 2答案是 2。路径 2 - 3 - 4两步正确。查询 (4, 2)。b 在环上posInCyc[2] 0posInCyc[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 乘 LOG2e5 乘 20400 万个 int约 16MB。加上其他数组总内存也就二三十 MB同样很宽松。7.2 LOG 怎么选常数怎么优化这里有一个优化小技巧查询循环里的跳跃可以用 for k 从 LOG-1 往下扫也可以从 0 往上扫。两种写法在二进制拆分时效果一样但从 0 往上扫更贴合 need 的二进制表示而且不容易出现跳过头的问题。我自己习惯从 0 往上扫理由是 need 最多只有 LOG 位逐位看就好不用考虑大端小端。如果遇到极端数据比如环非常长、树非常深depth 可能达到 1e5 量级up 表依然扛得住。只要 LOG 取到 18 以上就不会跳不到。我见过有人把 LOG 设成 15结果在 n2e5 的链上直接错原因就是 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 ba 和 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 这几个数组的语义用注释写在代码最上面再开始动手。每个数组是什么含义、存的是什么值、用在哪个公式里都写清楚之后写查询分支时就能做到逐行对上逻辑而不是边写边猜。这个习惯帮我省下了非常多调试时间。