两种移动各自沿一条固定链,用两套倍增表把"跳 a 步"压到 O(log n)。
给定一棵有 n 个结点的有根树,结点依次以 1, 2, …, n 编号,其中根结点的编号为 1。
小 A 计划在这棵有根树上进行 q 次旅行。在第 i 次旅行中,小 A 首先选定结点 sᵢ 作为起点,并移动若干次。移动分为以下两种:
由于移动次数可能很大,对于第 i 次旅行,旅行中的移动以 kᵢ 个不为零的整数构成的序列 ai,1, ai,2, …, ai,kᵢ 表示:若 ai,j > 0 则代表进行 ai,j 次第一种移动;若 ai,j < 0 则代表进行 −ai,j 次第二种移动。根据给出的序列从左至右完成所有移动后,小 A 所在的结点即是旅行的终点。
输入格式:第一行两个正整数 n, q;第二行 n − 1 个整数 p₂, p₃, …, pₙ(pᵢ 是结点 i 的父结点);接下来 2q 行中,第 2i − 1 行是 sᵢ, kᵢ,第 2i 行是 kᵢ 个整数 ai,1 … ai,kᵢ。
输出格式:共 q 行,第 i 行为第 i 次旅行的终点编号。
输入输出样例 1
| 输入 | 输出 |
|---|---|
5 4 | 4 |
输入输出样例 2
| 输入 | 输出 |
|---|---|
8 3 | 1 |
数据范围:1 ≤ n ≤ 10⁵,1 ≤ q ≤ 2 × 10⁴,kᵢ ≥ 1、Σkᵢ ≤ 10⁵,1 ≤ |ai,j| ≤ n。
a 次就是沿"父亲链"往上走 a 格;minch(u)),跳 a 次就是沿这条"最小儿子链"往下走 a 格。O(log n)。有根树固定后继倍增两套跳跃表原地不动(自环)
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、q;第二行 n − 1 个父结点;随后 2q 行是旅行数据 |
| 输出 | q 行,每次旅行的终点 |
| 数据范围 | 1 ≤ n ≤ 10⁵,1 ≤ q ≤ 2 × 10⁴ |
| 序列总长 | Σkᵢ ≤ 10⁵,|a| ≤ n |
| 移动① | 去父结点;根结点不动 |
| 移动② | 去编号最小的子结点;叶子结点不动 |
| 子任务 | 20% |a| = 1;20% 只有移动①;20% 只有移动②;40% 无限制 |
|a| 可以到 10⁵,而 Σk ≤ 10⁵,最坏 10⁵ × 10⁵ = 10¹⁰ 步,必然超时up₀(u) = p_u(根记为自己);向下:dn₀(u) = minch(u)(叶子记为自己)up 表会在根处"断掉",后续合成 up[j][u] = up[j−1][up[j−1][u]] 会读到非法下标或算错(比如"从根出发往上跳 3 次,再往下跳 2 次"这类混合操作)10⁵ 深的链,递归 dfs 会爆栈;好在这题连 DFS 都不需要——父结点直接给出,只要扫一遍 i = 2 … n 求 minch,再按 j 递增合成倍增表即可样例 1 的父结点数组是 1 1 2 2,即 p₂ = 1, p₃ = 1, p₄ = 2, p₅ = 2。
| 结点 u | 父结点 p_u | 儿子列表 | minch(u) | 说明 |
|---|---|---|---|---|
| 1 | (根,记为自己) | {2, 3} | 2 | 根向上不动 |
| 2 | 1 | {4, 5} | 4 | 编号最小的儿子是 4 |
| 3 | 1 | (空) | — | 叶子,向下不动 |
| 4 | 2 | (空) | — | 叶子,向下不动 |
| 5 | 2 | (空) | — | 叶子,向下不动 |
3 执行 +1(去父结点):3 → 1
1 执行 −1(去最小儿子 2):1 → 2
2 执行 −1(去最小儿子 4):2 → 4
终点 4
✅ 4
2 --+1--> 1
1 ---−1--> 2
2 --+1--> 1
1 ---−1--> 2
2 --+1--> 1
来回横跳 5 次,最后停在 1
✅ 1
5 --+1--> 2 --+1--> 1 --+1--> 1(根向上不动!)
1 ---−1--> 2 ---−1--> 4 ---−1--> 4(叶子向下不动!)
再执行两次 −1,仍然停在 4
这里同时考到了"根不动"和"叶子不动"两个自环
✅ 4
5 ---−1--> 5(叶子不动)
5 ---−1--> 5(还是叶子)
5 --+1--> 2
终点 2
✅ 2
4
1
4
2 ✓
样例 2 的 p₂ … p₈ = 5 4 2 1 3 6 6,父亲关系是 2→5→1、4→2、3→4、6→3、7→6、8→6。
| 结点 u | 父结点 | 儿子列表 | minch(u) |
|---|---|---|---|
| 1 | (根) | {5} | 5 |
| 2 | 5 | {4} | 4 |
| 3 | 4 | {6} | 6 |
| 4 | 2 | {3} | 3 |
| 5 | 1 | {2} | 2 |
| 6 | 3 | {7, 8} | 7(编号最小的儿子) |
| 7 | 6 | (空) | — |
| 8 | 6 | (空) | — |
8 --+8--> 6 --+7--> 3 --+6--> 4 --+5--> 2 --+4--> 5 --+3--> 1
还剩 2 步:1 是根,继续不动
所以 8 步后停在 1
注意这里"向上跳"其实是沿父亲链:8→6→3→4→2→5→1
✅ 1
先 +8:8 → 1(同上)
再 −8:从 1 沿"最小儿子链"往下走 8 步
1→5→2→4→3→6→7→7→7
第 6 步到 7 之后,7 是叶子,后续两步原地不动
✅ 7
8 → 1(+8)
1 → 7(−8,如上一行)
7 --+8--> 6 --+7--> 3 --+6--> 4 --+5--> 2 --+4--> 5 --+3--> 1
最后 2 步贴在根上不动,停在 1
✅ 1
minch(7) = 0 导致跳到非法结点),答案就会直接错。up[j][u] 与 dn[j][u] 分别表示"向上/向下跳 2ʲ 步"的结果,每次移动 O(log n)
每一步都真的移动一次,逻辑最直白
|a| 与 n 同阶(都到 10⁵),而 Σk 也到 10⁵,两者一乘就是 10¹⁰ 步。| 方案 | 复杂度 | 结论 |
|---|---|---|
| 两套倍增表 | O((n + Σk) log n) ≈ 4 × 10⁶ | ✅ 正解(官方做法) |
| 逐步模拟 | O(Σk × |a|) 最坏 10¹⁰ | ❌ 严重超时,只拿部分分 |
| 只处理 |a| = 1 的子任务 | O(n + Σk) | ❌ 仅 20 分 |
第一行输入 n q,第二行输入 n − 1 个父结点,随后 2q 行依次输入每次旅行的「起点 序列长度」与「移动序列」。程序会逐步走出终点并给出轨迹。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; // n ≤ 10^5,保险起见开到 2 × 10^5 const int LOG = 19; // 2^19 = 524288,足够覆盖 n int par[MAXN], minch[MAXN]; int up[LOG][MAXN], dn[LOG][MAXN]; int main() { int n, q; scanf("%d %d", &n, &q); par[1] = 1; // 根的父亲记为自己 → 向上自环 for (int i = 2; i <= n; i++) scanf("%d", &par[i]); for (int i = 1; i <= n; i++) minch[i] = 0; // 0 表示没有儿子 for (int i = 2; i <= n; i++) { int p = par[i]; if (minch[p] == 0 || i < minch[p]) minch[p] = i; // 记下编号最小的儿子 } for (int u = 1; u <= n; u++) { up[0][u] = par[u]; // 一步向上(根仍是自己) dn[0][u] = (minch[u] == 0 ? u : minch[u]); // 一步向下(叶子仍是自己) } for (int j = 1; j < LOG; j++) for (int u = 1; u <= n; u++) { up[j][u] = up[j-1][ up[j-1][u] ]; dn[j][u] = dn[j-1][ dn[j-1][u] ]; } while (q--) { int s, k; scanf("%d %d", &s, &k); int cur = s; for (int i = 0; i < k; i++) { int a; scanf("%d", &a); if (a > 0) { // 向上跳 a 步 for (int j = 0; a; j++, a >>= 1) if (a & 1) cur = up[j][cur]; } else { // 向下跳 −a 步 int t = -a; for (int j = 0; t; j++, t >>= 1) if (t & 1) cur = dn[j][cur]; } } printf("%d\n", cur); } return 0; }
up[0][1] = 1、dn[0][leaf] = leaf 两条自环是整段代码正确性的基石,千万不要写成 0;② 合成公式 up[j][u] = up[j−1][ up[j−1][u] ] 要求 up[j−1][u] 一定是合法结点,自环恰好保证了这一点;③ 整个建表过程只有两层循环,没有递归,链状数据也不会爆栈。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
par[1] = 1; | 向上自环 | 根再往上还是根,避免越界与特判 |
if (minch[p] == 0 || i < minch[p]) minch[p] = i; | 求最小编号儿子 | 只比编号,不要写"最小的后代" |
dn[0][u] = (minch[u] == 0 ? u : minch[u]); | 向下自环 | 叶子往下还是叶子 |
up[j][u] = up[j-1][ up[j-1][u] ]; | 倍增合成 | 跳 2ʲ = 先跳 2ʲ⁻¹ 再跳 2ʲ⁻¹ |
for (int j = 0; a; j++, a >>= 1) if (a & 1) ... | 按二进制位跳 | 把 a 拆成 2 的幂之和,逐步查表 |
up[0][1] 写 0,倍增越界);② 忘了"叶子向下不动"(dn[0] 写 0);③ minch 理解成"编号最小的后代"而不是"编号最小的儿子";④ 递归建树:链状数据 10⁵ 深,直接爆栈;⑤ 用 for (int i = 0; i < a; i++) 一步一动(|a| 到 10⁵,总步数 10¹⁰,超时)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 4 | 4 1 4 2 | 题面样例 1(含根不动、叶子不动) |
8 3 | 1 7 1 | 题面样例 2(父结点编号可以大于子结点) |
2 2 | 1 2 | 最小规模:1←→2 往返 |
3 2 | 1 2 | 根贴顶不动(+5 后仍在 1)、叶子不动后换了方向 |
5 2 | 1 5 | 链上走到底再走回来;叶子向下不动 |
up[0][1] = 1 了吗?② dn[0][叶子] = 叶子 了吗?③ 倍增表是"迭代合成"而不是递归吗?④ 每次移动是按二进制位跳而不是逐格走吗?up[0][根] 与 dn[0][叶子] 必须指向自己,否则倍增表会在边界处算错。⌊log₂ n⌋ + 1;n = 10⁵ 时 17 层刚好够,建议直接开到 18 ~ 19。|a| ≤ n 且 Σk ≤ 10⁵,最坏 10¹⁰ 步,只能拿部分分。minch:扫一遍 i = 2 … n,O(n)LOG × n 次赋值,LOG = 19 时约 1.9 × 10⁶ 次(两张表 3.8 × 10⁶)|a| 拆成二进制,最多 LOG 次查表Σk ≤ 10⁵,所以旅行部分约 10⁵ × 19 = 1.9 × 10⁶两张表 up、dn 各 LOG × (n + 1) 个 int:2 × 19 × 10⁵ × 4 B ≈ 15 MB;再加父结点、minch 等数组,内存远低于 256 MB。
✅ 预处理约四百万次赋值 + 旅行约两百万次查表,总共不到一千万次基础操作,1 秒时限轻松过。
真正需要小心的不是时间而是细节正确性:两条自环 + 迭代建表,缺一个就可能 WA 或 RE。
// 「后继函数唯一 + 步数巨大」→ 倍增(binary lifting)通用模板 // 1) 先写"跳一步"的函数:nxt0[u] = 某个唯一确定的后继 // 2) 把"走不动"的情况写成自环:nxt0[u] = u(而不是 0) // 3) 合成:nxt[j][u] = nxt[j-1][ nxt[j-1][u] ] // 4) 查询"跳 a 步":把 a 拆成二进制位 int cur = s; for (int j = 0; a; j++, a >>= 1) if (a & 1) cur = nxt[j][cur]; // 本题有两套后继函数,所以要两张表: // up[0][u] = 父结点(根为自己) // dn[0][u] = 编号最小的子结点(叶子为自己) // 没有递归:父结点数组直接给出,扫一遍就能求 minch 与两张表 // 如果题目是"无根树 + 给定每次跳跃方向",那就先迭代 DFS/BFS 求父结点和深度 // 类似的"沿固定链跳 a 步"问题: // · 树上第 k 级祖先(经典倍增 LCA) // · 函数图上的第 k 次迭代(每个点出度恰好为 1) // · 自动机 / 置换群的幂
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 后继函数 + 自环 | 把"根不动 / 叶子不动"写成 up[0][根] = 根 | 函数图第 k 次迭代、循环节类问题(有界状态必须自环) |
| 倍增合成 | up[j][u] = up[j−1][up[j−1][u]] | 第 k 级祖先、LCA、稀疏表、快速幂(思想同源) |
| 按二进制位拆分步数 | 跳 a 步被拆成 log a 次查表 | 任何"大跨度查询"都能这样分解成 O(log) 次 |
| 迭代预处理代替递归 | 直接扫父结点数组求 minch,不做递归 DFS | 所有 n 到 10⁵ ~ 10⁶ 的树题都要防爆栈 |
minch 换成 maxch(求儿子编号的最大值),其余倍增结构一行都不用改——因为"后继唯一"这个性质没变。