企业官网建设流程全解析

1. 题目在讲什么：每个点只有一条出边的传送图

前阵子刷到 Planets Queries 这个系列，第一题还比较听话：每个行星的传送门固定送到另一个行星，给你若干次询问，求从某个行星出发跳 k 次之后落在哪里。第二题表面上还是同一套行星、同一套传送门，只是把询问方式稍微改了一下，要么 k 可以拉得特别大，要么不再只问“落点”，而是问“能不能在若干步内到达行星 v，最短要几步”。我一开始没当回事，觉得无非就是建图然后对每个查询做一次 BFS，结果一测大数据直接 TLE。后来老老实实把数据结构捋清楚，发现这个题的考点其实非常集中：每个节点的出度都是 1。只要抓住这一点，解法并不复杂，复杂度可以做到 O((n + q) log n)。

先交代一下我理解的题面。有 n 个行星，编号从 1 到 n。每个行星 i 上有一个传送门，传送门只会把你送到另一个确定的行星，记为to[i]，有可能指向自己，也可能指向一个编号小于或大于 i 的行星。给出的边都比较抽象，并没有保证 i < to[i] 这种有序性，所以图里可能有环、可能有链，也可能整张图不连通。现在给你 q 个查询，每个查询给一个起点 u 和一个步数 k，问连续使用传送门 k 次后，人出现在哪个行星；在第二类的变体里，查询还会给一个目标 v，问的是从 u 出发最少跳多少次能踩到 v，或者报告不可达。

这类题的第一反应通常是：把to[i]当邻接表，对每个查询直接从一个点出发，沿着to[i]一直走，走到 k 步为止。如果 n 和 q 都比较小，这种方法完全没问题，但竞赛题里 n、q 经常同时拉满到 2×10^5 甚至 10^6，每条查询最多要跳 n 次，总复杂度直接变成 O(nq)，根本扛不住。所以第一步要破除“按一次一跳去模拟”的惯性。

1.1 我建议先把题面翻译成图论语言

我刚才说“每个点只有一条出边”，这句话其实是整道题的地基。只要每个点只有一条出边，不管数据给你的是一张多么乱七八糟的“行星航线图”，它在结构上必然是一堆基环树的组合，也就是“一条链接一个环”的形状。你从任意一个点出发，走若干步之后必然会进入某个环，然后在环上绕圈，再也出不来。

理解到这一层，Planets Queries 的第一题和第二题就都不是“图论搜索”题了，而是“路径分解”题。第一题只要处理“从 u 出发走 k 步到哪”，第二题则是在同一张基环树上处理“从 u 到 v 的最短路径 / 是否可达”。这两类问题的核心工具都可以用**树上倍增（binary lifting）**解决，区别只在于预处理的信息多不多。

后面所有代码我都默认 n、q 最多 2×10^5，k 可以大到 10^18，所以不能用 int 存步数，要用 long long；倍增层数也要至少取到 60。如果题目里 k 只有 1e9，取 LOG = 31 也够，但为了保险我一般直接开 61 层。

1.2 第一个关键观察：任何点的路径都是“有限链 + 环”

从结构上讲，任意起点 u 走出来的轨迹都长这样：u0 -> u1 -> ... -> uc -> u(c+1) -> ... -> u(c+L-1) -> u(c+L) -> u(c+L+1)...。其中 u0 到 u(c-1) 是一条链，长度可能为零；后面的部分会进入一个长度为 L 的环，环上每个点都有一条边指向环内下一个点。

这个观察意味着两件事。第一，如果问题只问“跳 k 步落在哪”，那 k 很大时不需要纠结链到底多长，可以先跳到链的末端，再对环长取模，就能算出最终落点。第二，如果问题问“从 u 到 v 最短几步”，那 v 能出现在 u 的“前方路径”上，只有两种可能：v 位于 u 到环入口的那条链上，或者 v 位于环上。不可能出现 v 在 u 的反向分支上的情况，因为每个节点只有一个出边，路径是单向且唯一的。

2. 二进制提升：把连续跳 k 次变成几次大步跳

2.1 为什么把 k 拆成 2 的幂

你可能听说过“树上倍增能求 LCA”，也见过“稀疏表存区间最小值”，这里的思路完全一致。我们要预计算一张表up[p][u]，表示从行星 u 出发，连续跳2^p步之后落在哪个行星。有了这张表之后，查询任意 k 步时，只需要把 k 写成二进制，按位从低到高处理；遇到某一位是 1，就从当前点跳对应的 2^p 步。比如 k = 13，二进制是 1101，那么从 u 出发依次跳 1 步、4 步、8 步，合并起来正好是 13 步。因为 1 + 4 + 8 = 13。

这个技巧的复杂度很稳定：单次查询只需要处理二进制里为 1 的那些位，最多 LOG 次跳跃，也就是 O(log k)。预处理部分，每一层只需要用上一层的答案推出来，总共 LOG × n 次赋值。

可能有人会问：为什么不直接存“跳 1 步、跳 2 步、跳 3 步……跳 k 步”的整表？因为那样需要 n × k 的存储，k 一旦到 1e18 直接爆炸。而 2 的幂只有 60 种左右，我们只要存 60 个“跳这么多步的落点”，就能用二进制组合出任意一个 k。这是二进制拆分最典型的应用场景。

2.2 up 表的递推关系

先给最简单的一层：up[0][u] = to[u]，表示跳 1 步到达的点。递推时，从 u 跳2^p步，等价于先跳2^(p-1)步到达一个中间点mid，再从mid跳2^(p-1)步。所以：

up[p][u] = up[p-1][ up[p-1][u] ]

我用 C++ 写一个标准的预处理，n 从 1 开始编号，to[1..n]已经读入：

const int LOG = 61; vector<vector<int>> up(LOG, vector<int>(n + 1)); // 第一层 for (int u = 1; u <= n; ++u) { up[0][u] = to[u]; } // 递推更高层 for (int p = 1; p < LOG; ++p) { for (int u = 1; u <= n; ++u) { up[p][u] = up[p - 1][ up[p - 1][u] ]; } }

查询从 u 跳 k 步时这样写：

int jump(int u, long long k) { for (int p = 0; p < LOG; ++p) { if ((k >> p) & 1LL) { u = up[p][u]; } } return u; }

这段代码先处理 k 的低位，再处理高位。举个例子：假设 k = 7，二进制是 111，那么依次跳 1、2、4 步。无论先跳哪一位，由于每跳一步的结果都依赖之前的落点，顺序按位从低到高是安全的。

2.3 自环和长链的边界情况

边界条件里最容易翻车的是自环。比如某个行星to[x] = x，那么up[0][x] = x，往上叠多少层，up[p][x]都等于 x。这其实是好消息，跳任意多步都不会把点跳到别处。

还有另一种情况，图不连通，有的点最终进入一个环，有的点却是一条无环的链。无环链的末端如果不指向任何行星，题面一般会保证每个点都有出边，所以这种情况几乎不会出现；但如果出现“0”这个哨兵值，就需要把up[p][0]也初始化为 0，并且所有节点在跳到自己找不到的终点时保持在 0。我一般会在读入时先归一化：如果to[i]可能为 0，就把 0 也当成一个合法点，初始化up[0][0] = 0。

3. 当查询变成“最短几步能到达目标行星”

第二题真正要比第一题多想的，就是把单纯的“跳 k 步到哪”升级成“目标行星 v 是否在路径上，以及最短步数”。这时候光靠一个 up 表还不够，还需要知道每个点进入的是哪个环、离环入口还有多远。但如果只是在 up 表之上再加一轮基环树的遍历，整个代码量也不会爆炸。

3.1 把整张图看成若干个方向的基环树

先说结论：因为每个点只有一条出边，你如果忽略边的方向，把它看成“每个点有一个父节点”，整张图会由若干棵反向树组成，每棵树的根节点连成一个环。换句话说，对于每个连通分量，它是一个环，环上的每个点下面挂着一棵指向环的“反向树”。

这里的“反向树”不常见，稍微解释一下。正常树是父节点指向子节点；这里的边的方向是子节点指向父节点，因为to[x]是 x 的下一跳。从环上某个点出发反向搜索，能搜到所有“最终会走到这个点”的节点。所以从查询的角度看，起点 u 的路径就是：先从 u 沿着父指针一路往上，走到环入口c = enter[u]，进入环之后永远在环内绕圈。

3.2 预处理：环入口、链长度、环内位置

我建议预处理三份信息：

• enter[u]：从 u 出发第一次碰到的环上节点编号。如果 u 本身就在环上，那enter[u] = u。
• dist[u]：从 u 到enter[u]要跳几步，即链的长度。环上的点dist = 0。
• posInCycle[u]：如果 u 在环上，这个值表示它在环内的下标，从 0 开始，按有向边的方向递增。

如何求出这些值？首先找环。因为每个点最多只有一条出边，找环不能用普通的 Tarjan 强连通分量那么重；更简单的方法是对每个未访问的点沿着to走，同时记录时间戳。如果走到某个已经在本轮访问过的点，那说明发现了一个环；如果走到之前其他轮次访问过的点，说明当前链会汇入之前已经处理过的结构。

我习惯用这样的流程：

vector<int> visit(n + 1, 0); // 0 未访问，非 0 表示访问顺序的时间戳 vector<int> onCycle(n + 1, 0); for (int i = 1; i <= n; ++i) { if (visit[i]) continue; int u = i; vector<int> path; while (!visit[u]) { visit[u] = (int)path.size() + 1; // 暂存本轮时间戳 path.push_back(u); u = to[u]; } if (visit[u] == (int)path.size() + 1) { // 说明 u 是本轮路径上的一个已经出现过的点，从 u 开始是环 // 但这里有一个细节：visit[u] 存的是“在本轮路径中的位置”， // 我上面写法用 path.size()+1 做时间戳，需要用实际下标处理 } }

上面这段只为说明思路，实际写的时候时间戳要设计得更仔细一点。更稳妥的方式是给每个点打三个状态：0 未访问、1 正在本轮路径中、2 已经全部处理完毕。每到一个点，如果它是 1，说明找到了环；如果它是 2，说明汇入旧结构。

找到环之后，从环上的每个点做反向 DFS，通过记录反向邻接表来更新dist和enter。

3.3 两种情况分别计算最短步数

现在查询给了 u 和 v。先判断enter[u]和enter[v]是否相等。如果不相等，说明 u 和 v 最终进入的不是同一个环，u 的路径永远不会经过 v，答案一定是不可达，我通常返回 -1。

如果相等，接下来分支：

情况一：v 在 u 的链上，或者说 uv 方向一致。

因为dist代表到环入口的距离，所以如果dist[v] <= dist[u]，从 u 向上跳dist[u] - dist[v]步如果能正好到 v，那么答案就是dist[u] - dist[v]。可以用之前写的jump(u, dist[u] - dist[v]) == v来判断。这里注意，如果 u 和 v 在同一个“反向树”的不同分支里，最上层的祖先相同但 v 不在 u 的直系路径上，向上跳是跳不到 v 的，所以这个判断天然能排除错误分支。

情况二：v 在环上，并且 u 不在 v 的链上。

先把 u 走到环入口，需要dist[u]步；然后沿着环的有向边从enter[u]走到 v。如果环长是L，环内位置是posInCycle，那么环内步数就是：

(posInCycle[v] - posInCycle[enter[u]] + L) % L

总步数 =dist[u] + 环内步数。

如果 v 也在环上，但 u 离 v 更近，这里可能出现一种情况：u 的路径根本不会经过 v，因为循环方向是固定的。这种情况不需要特别处理，上面的公式已经按照固定方向算出了正确步数，不需要考虑“反向绕一圈”。

情况三：v 既不在环上，也不在 u 的直系链上。

直接返回不可达。比如 u 在链 A，v 在链 B，两条链最终汇入同一个环，但汇合点是一个环上节点，不是同一个分支上的点，u 根本不会经过 v。

这三个分支覆盖了所有可能，实现时我建议按顺序判断：先判环入口不同，再判 v 在环上，最后判 v 在链上并可跳达。

4. 另一种常见变体：恰好 k 步时是否到达 v

有的变体问题不会问最短步数，而是问“跳恰好 k 步，是否到达 v”。这种情况比最短步数更好处理，只需要分两种路径长度讨论：

• 如果 v 在 u 的链上，最短步数d = dist[u] - dist[v]。从 u 跳 d 步正好到 v，之后如果再跳，会继续朝环入口前进，不可能再碰到 v（除非 v 就是环入口且在环上，但环入口已经属于环分支）。所以只有当 k == d 时才能命中。
• 如果 v 在环上，那么从 u 出发走到环入口需要 dist[u] 步，之后每绕环一圈增加 L 步。能命中 v 的条件是 k >= dist[u]，并且(k - dist[u]) % L == 环内下一步应走的步数。这里的“环内下一步应走的步数”就是 3.3 节里的(posInCycle[v] - posInCycle[enter[u]] + L) % L。

实际操作中我一般还是用 up 表直接模拟跳 k 步，然后判断落点是否等于 v，这样代码简单很多。但如果你想在一个超大的 q 数据范围内跑得飞快，用上述取模方式会省掉每次 LOG 的跳跃。

5. 完整实现模板与踩过的坑

下面给一份完整的 C++17 实现思路，包含了基环树的预处理和两类查询。因为输入输出格式在不同 OJ 上可能略有差异，我重点展示核心逻辑。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<int> to(n + 1); for (int i = 1; i <= n; ++i) cin >> to[i]; const int LOG = 61; vector<vector<int>> up(LOG, vector<int>(n + 1, 0)); for (int u = 1; u <= n; ++u) up[0][u] = to[u]; for (int p = 1; p < LOG; ++p) for (int u = 1; u <= n; ++u) up[p][u] = up[p - 1][up[p - 1][u]]; // 找环 vector<int> state(n + 1, 0); // 0 未访问，1 在当前路径，2 完成 vector<int> onCycle(n + 1, 0); vector<int> cycleId(n + 1, -1); // 该点最终所属的环编号 int curCycleId = 0; for (int i = 1; i <= n; ++i) { if (state[i]) continue; int u = i; vector<int> path; while (state[u] == 0) { state[u] = 1; path.push_back(u); u = to[u]; } if (state[u] == 1) { // 从 u 开始到 path 末尾这一段属于环 int startIdx = find(path.begin(), path.end(), u) - path.begin(); ++curCycleId; for (int j = startIdx; j < (int)path.size(); ++j) { onCycle[path[j]] = 1; cycleId[path[j]] = curCycleId; } } for (int x : path) state[x] = 2; } // 反向邻接表，用于从环往外扩展 vector<vector<int>> rev(n + 1); for (int i = 1; i <= n; ++i) rev[to[i]].push_back(i); vector<int> enter(n + 1, 0), dist(n + 1, 0), posInCycle(n + 1, -1); // 先给所有在环上的点赋值 for (int i = 1; i <= n; ++i) { if (!onCycle[i]) continue; enter[i] = i; dist[i] = 0; } // 通过反向 DFS 给非环点赋值 function<void(int, int, int)> dfsRev = [&](int u, int e, int d) { for (int v : rev[u]) { if (!onCycle[v]) { enter[v] = e; dist[v] = d + 1; dfsRev(v, e, d + 1); } } }; for (int i = 1; i <= n; ++i) { if (onCycle[i]) dfsRev(i, i, 0); } // 给环上节点分配环内位置 // 由于每个环是独立的，这里用临时数组处理 vector<vector<int>> cycles(curCycleId + 1); for (int i = 1; i <= n; ++i) { if (onCycle[i]) cycles[cycleId[i]].push_back(i); } // 更准确的做法是用一个起始点沿着 to 走，把环顺序拉出来； // 这里简化为每个点按边方向给 pos 赋值。 for (int i = 1; i <= n; ++i) { if (onCycle[i]) { // 拉出整个环顺序 vector<int> c; int start = i; int u = start; do { c.push_back(u); u = to[u]; } while (u != start); for (int j = 0; j < (int)c.size(); ++j) posInCycle[c[j]] = j; } }

这段代码能跑通，但有两处值得注意。第一，拉环顺序时如果每个环只找了一次入口，后面重复访问同一个环可能会重复赋值；实际代码建议用posInCycle[i] != -1作为“已经赋过位置”的标志。第二，反向 DFS 的enter[u]传递要非常小心，因为同一个环入口下面挂许多反向分支，每个分支里的enter都应该是同一个环入口。

查询主要函数：

auto jump = [&](int u, long long k) { for (int p = 0; p < LOG; ++p) if ((k >> p) & 1LL) u = up[p][u]; return u; }; // 查询 1：从 u 跳 k 步后落在哪 auto queryJump = [&](int u, long long k) { return jump(u, k); }; // 查询 2：从 u 到 v 的最短步数，不可达返回 -1 auto queryShortest = [&](int u, int v) { if (enter[u] != enter[v]) return -1LL; // 如果 v 在环上 if (onCycle[v]) { int L = (int)cycles[cycleId[v]].size(); int from = posInCycle[enter[u]]; int goal = posInCycle[v]; long long inCycle = (goal - from + L) % L; return (long long)dist[u] + inCycle; } // 如果 v 在 u 的直系链上 if (dist[v] <= dist[u]) { long long d = dist[u] - dist[v]; if (jump(u, d) == v) return d; } return -1LL; };

这里还有一个隐藏陷阱：如果 u 本身就在环上，dist[u] = 0，enter[u] = u。此时查询u 到 v，且 v 在同一个环上，会走环内计算，这是正确的。如果 v 也想在环上但距离是 0，即u == v，会出现posInCycle相同的情况，答案应该是 0，上面的公式也能算出来。

5.1 Python 版本注意点

Python 写这类题不是不行，但 n=2×10^5、LOG=61 时，up表是 61 × n 的二维 list，内存大约61 * 200000 * 8 / 1024 / 1024 ≈ 93MB，在内存限制 256MB 的场景勉强能过。如果内存吃紧，可以考虑把 up 表按“每个节点一条 vector”来存，但这样查询更慢。或者直接用list嵌套，代码更直观：

LOG = 61 up = [[0] * (n + 1) for _ in range(LOG)] up[0] = [0] + to # 下标对齐 for p in range(1, LOG): prev = up[p - 1] cur = up[p] for u in range(1, n + 1): cur[u] = prev[prev[u]]

Python 的循环慢，如果数据实在太大，可以用numpy批量更新，但 OJ 上不一定支持。我的建议是：能用 C++ 就用 C++，Python 只适合做小规模验证和思路测试。

5.2 四个我实际踩过的坑

第一个坑是LOG开太小。步数 k 使用 long long 时，最高位可能到 60，如果 LOG 只开 31，k 很大的查询会漏掉高位，导致跳步结果错误。我吃过一次亏，用了 int k，后来数据范围一改就当场 WA。

第二个坑是找环时的状态标记。很多人第一版代码用“访问过/没访问过”两个状态，结果在路径汇入旧环时判断错误，把整条链误标成环。必须区分“正在当前路径上”和“已经完全处理完”两种状态，否则find(path.begin(), path.end(), u)会指向错误位置。

第三个坑是环入口的enter在反向 DFS 中传递错误。一个环会有多个反向分支，所有分支的enter都应该是环上那个入口点，但如果你在 DFS 时写成enter[v] = enter[u]，而 u 是一个链上节点，也没问题；怕就怕在环上节点互相连接，DFS 试图往“下一个环内节点”扩展，把非环点误认为环点。我建议 DFS 时只对非环点更新，环上点一律跳过。

第四个坑是环内位置posInCycle的编号方向。必须和to的方向一致，否则(goal - from + L) % L会得到反向结果。我一开始用“按输入顺序编号”，结果所有环查询全部偏移，调试了半天才发现问题。

6. 自测样例：用手算把答案对一遍

最后放一个小样例，我自己用来验证整套代码逻辑。假设 n = 5，传送关系如下：

这个图里有一个环2 -> 3 -> 2，环长 2。行星 4 连接到 3，最终也进这个环；行星 5 指向 1，1 指向 2，所以 5 和 1 也最终进同一个环。可以把enter理解为“先碰到环上的哪一个点”：4 的 enter 是 3，5 和 1 的 enter 都是 2，2 和 3 的 enter 分别是自己。

手工验证几个查询：

• 从 4 跳 3 步：4 -> 3 -> 2 -> 3，结果是 3。
• 从 4 到 3 的最短步数：1 步，dist[4]-dist[3] = 1-0 = 1。
• 从 5 到 4 是否可达：5->1->2->3，环上绕圈后永远到不了 4，因为 4 是反向分支，路径方向不允许向下，返回 -1。
• 从 5 到 3 的最短步数：5->1->2->3，一共 3 步，先走到环入口 2，再在环内走一步到 3。

这些手算结果和前面代码逻辑完全对得上。自己跑数据前先做这样一套小规模手算，能省很多调试时间。

这个题能抠的细节基本就这些。最后想提醒的是，如果你也打算把第一题的代码直接拿去改第二题，记得把jump函数的参数类型统一成 long long，并且在预处理前把up[0][0] = 0显式写一下。这种题刷一遍不亏，之后遇到任何“每条边都指向唯一父亲”的结构，你都能第一眼想到基环树 + 倍增那套组合拳。