GESP 题解库 / 8 级题解 / [GESP202506 八级] 树上旅行 · 第 8 / 24 题
GESP202506 八级 · P13019 · 困难

树上旅行

两种移动各自沿一条固定链,用两套倍增表把"跳 a 步"压到 O(log n)。

🌲
n ≤ 10⁵
有根树结点数
🧭
q ≤ 2×10⁴、Σk ≤ 10⁵
旅行数与序列总长
⚡
O((n + Σk) log n)
两套倍增
🎯
向上跳 + 沿最小子结点跳
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定一棵有 n 个结点的有根树,结点依次以 1, 2, …, n 编号,其中根结点的编号为 1。

小 A 计划在这棵有根树上进行 q 次旅行。在第 i 次旅行中,小 A 首先选定结点 sᵢ 作为起点,并移动若干次。移动分为以下两种:

  1. 移动至当前结点的父结点。特殊地,如果当前位于根结点,则不进行移动。
  2. 移动至当前结点的所有子结点中编号最小的结点。特殊地,如果当前位于叶子结点,则不进行移动。

由于移动次数可能很大,对于第 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
1 1 2 2
3 3
1 -1 -1
2 5
1 -1 1 -1 1
5 8
1 1 1 -1 -1 -1 -1 -1
5 3
-1 -1 1
4
1
4
2

输入输出样例 2

输入输出
8 3
5 4 2 1 3 6 6
8 1
8
8 2
8 -8
8 3
8 -8 8
1
7
1

数据范围:1 ≤ n ≤ 10⁵,1 ≤ q ≤ 2 × 10⁴,kᵢ ≥ 1、Σkᵢ ≤ 10⁵,1 ≤ |ai,j| ≤ n。

💡
人话翻译:把两种移动分别看成一条固定链上的跳跃。
· 移动①(去父结点):每个结点只有唯一的起点,跳 a 次就是沿"父亲链"往上走 a 格;
· 移动②(去编号最小的子结点):每个结点的"下一站"是唯一的(minch(u)),跳 a 次就是沿这条"最小儿子链"往下走 a 格。
既然"下一站唯一",就可以预处理出"跳 2ʲ 步会到哪"——这就是倍增。
两种移动各建一套倍增表(向上 / 向下),每做一次移动只需 O(log n)。
关键细节:根往上还是根、叶子往下还是叶子——把这两条"自环"写进倍增表第 0 层,后面所有合成就自动正确,不需要任何特判。

🔍 关键词提取

有根树固定后继倍增两套跳跃表原地不动(自环)

已知条件

项目说明
输入第一行 n、q;第二行 n − 1 个父结点;随后 2q 行是旅行数据
输出q 行,每次旅行的终点
数据范围1 ≤ n ≤ 10⁵,1 ≤ q ≤ 2 × 10⁴
序列总长Σkᵢ ≤ 10⁵,|a| ≤ n
移动①去父结点;根结点不动
移动②去编号最小的子结点;叶子结点不动
子任务20% |a| = 1;20% 只有移动①;20% 只有移动②;40% 无限制

需要解决的问题

02
思维导图
整理解题思路的全貌
🧭 两种移动 × 两套倍增表
🧠 问题本质
两种移动的"下一站"都是唯一确定的
跳 a 步 = 把同一个函数复合 a 次
函数复合满足结合律 → 可以倍增
根/叶子不动 = 自环,保证结合律不破
🧮 预处理
minch(u):编号最小的儿子(没有则为 0)
up[0][u] = 父结点(根为自己)
dn[0][u] = minch(u)(叶子为自己)
up[j][u] = up[j−1][up[j−1][u]],dn 同理
🏃 处理一次旅行
读入起点 s 与序列 a₁…a_k
aᵢ > 0:用 up 表把 aᵢ 的二进制位逐位跳
aᵢ < 0:用 dn 表跳 −aᵢ 步
每次移动 O(log n)
⚠️ 易错点
把 minch 当成"最小编号的后代"
根不漏自环 / 叶子漏自环
递归建树爆栈
倍增层数不够(要覆盖 n)
一次一次模拟导致超时
03
样例手算推导
样例 1 的四次旅行逐步走一遍

🧮 样例 1:先把树的形状画出来

样例 1 的父结点数组是 1 1 2 2,即 p₂ = 1, p₃ = 1, p₄ = 2, p₅ = 2。

结点 u父结点 p_u儿子列表minch(u)说明
1(根,记为自己){2, 3}2根向上不动
21{4, 5}4编号最小的儿子是 4
31(空)—叶子,向下不动
42(空)—叶子,向下不动
52(空)—叶子,向下不动
1
旅行 1:起点 3,序列 [1, −1, −1]

3 执行 +1(去父结点):3 → 1

1 执行 −1(去最小儿子 2):1 → 2

2 执行 −1(去最小儿子 4):2 → 4

终点 4

✅ 4

2
旅行 2:起点 2,序列 [1, −1, 1, −1, 1]

2 --+1--> 1

1 ---−1--> 2

2 --+1--> 1

1 ---−1--> 2

2 --+1--> 1

来回横跳 5 次,最后停在 1

✅ 1

3
旅行 3:起点 5,序列 [1, 1, 1, −1, −1, −1, −1, −1]

5 --+1--> 2 --+1--> 1 --+1--> 1(根向上不动!)

1 ---−1--> 2 ---−1--> 4 ---−1--> 4(叶子向下不动!)

再执行两次 −1,仍然停在 4

这里同时考到了"根不动"和"叶子不动"两个自环

✅ 4

4
旅行 4:起点 5,序列 [−1, −1, 1]

5 ---−1--> 5(叶子不动)

5 ---−1--> 5(还是叶子)

5 --+1--> 2

终点 2

✅ 2

📤 输出

4
1
4
2 ✓

🧮 样例 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
25{4}4
34{6}6
42{3}3
51{2}2
63{7, 8}7(编号最小的儿子)
76(空)—
86(空)—
1
旅行 1:起点 8,序列 [8]

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

2
旅行 2:起点 8,序列 [8, −8]

先 +8:8 → 1(同上)

再 −8:从 1 沿"最小儿子链"往下走 8 步

1→5→2→4→3→6→7→7→7

第 6 步到 7 之后,7 是叶子,后续两步原地不动

✅ 7

3
旅行 3:起点 8,序列 [8, −8, 8]

8 → 1(+8)

1 → 7(−8,如上一行)

7 --+8--> 6 --+7--> 3 --+6--> 4 --+5--> 2 --+4--> 5 --+3--> 1

最后 2 步贴在根上不动,停在 1

✅ 1

⚠️
两处"原地不动"是本题的命门:① 根结点执行第一种移动时不动;② 叶子结点执行第二种移动时不动。
样例 2 的旅行 2、旅行 3 都踩在这两个细节上:如果根没有自环(把它当成"跳不动就结束"或跳到 0),或者叶子没有自环(minch(7) = 0 导致跳到非法结点),答案就会直接错。
写代码时把这两条自环放在倍增表第 0 层,后面完全不用再写 if 判断。
04
解法对比
两套倍增 vs 逐步模拟 vs 贪心地只用一套表

⚔️ 解法对比

🟢 两套倍增表(推荐) 推荐

up[j][u] 与 dn[j][u] 分别表示"向上/向下跳 2ʲ 步"的结果,每次移动 O(log n)

  • 预处理 O(n log n)
  • 每次移动 O(log n)
  • 总复杂度 O((n + Σk) log n) ≈ 4 × 10⁶
  • 代码约 40 行
💡
为什么两种移动不能共用一张表:它们是两个不同的函数(一个是 u ↦ p_u,一个是 u ↦ minch(u)),复合的顺序和方向都不同。
把根/叶子写成自环后,两个函数各自都可以安全地复合 2ʲ 次,于是"跳 a 步"就是按 a 的二进制位拆开查表。

🟠 收到一次移动就 for 循环走 a 步

每一步都真的移动一次,逻辑最直白

  • 预处理 O(n)
  • 单次移动 O(|a|)
  • 最坏 O(Σk × n) = 10¹⁰
  • 只能过 |a| 很小的部分分
⚠️
为什么必挂:|a| 与 n 同阶(都到 10⁵),而 Σk 也到 10⁵,两者一乘就是 10¹⁰ 步。
这类"步数巨大但路径固定"的问题,倍增(或周期性/循环节)是标准出路。

📈 性能对比

方案复杂度结论
两套倍增表O((n + Σk) log n) ≈ 4 × 10⁶✅ 正解(官方做法)
逐步模拟O(Σk × |a|) 最坏 10¹⁰❌ 严重超时,只拿部分分
只处理 |a| = 1 的子任务O(n + Σk)❌ 仅 20 分
05
算法流程图
预处理两套倍增表 → 逐次旅行按位跳跃
开始读入 n、q 与父结点数组 p₂ … pₙ枚举 i = 2 … n,用 minch(pᵢ) 记录编号最小的儿子up[0][u] = 父结点(根为自己);dn[0][u] = minch(u)(叶子为自己)j 从 1 到 LOG − 1:up[j][u] = up[j−1][ up[j−1][u] ],dn 同理处理一次旅行:读入起点 s 与序列 a₁ … a_kaᵢ 是正数吗?是 ✓用 up 表向上跳 aᵢ 步否 ✗用 dn 表向下跳 −aᵢ 步本次旅行的序列还没走完吗?输出本次旅行的终点q 次旅行全部输出完毕取下一位 aᵢ
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🧭 树上旅行模拟器(逐步追踪)

第一行输入 n q,第二行输入 n − 1 个父结点,随后 2q 行依次输入每次旅行的「起点 序列长度」与「移动序列」。程序会逐步走出终点并给出轨迹。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(两套倍增表)

#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¹⁰,超时)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5 4
1 1 2 2
3 3
1 -1 -1
2 5
1 -1 1 -1 1
5 8
1 1 1 -1 -1 -1 -1 -1
5 3
-1 -1 1
4
1
4
2
题面样例 1(含根不动、叶子不动)
8 3
5 4 2 1 3 6 6
8 1
8
8 2
8 -8
8 3
8 -8 8
1
7
1
题面样例 2(父结点编号可以大于子结点)
2 2
1
2 1
1
1 2
-1 -1
1
2
最小规模:1←→2 往返
3 2
1 1
1 1
5
3 2
2 -2
1
2
根贴顶不动(+5 后仍在 1)、叶子不动后换了方向
5 2
1 2 3 4
1 2
-4 4
5 1
-4
1
5
链上走到底再走回来;叶子向下不动
✅
自查清单:① up[0][1] = 1 了吗?② dn[0][叶子] = 叶子 了吗?③ 倍增表是"迭代合成"而不是递归吗?④ 每次移动是按二进制位跳而不是逐格走吗?

🚨 易错点清单

⚠️
漏掉两条自环:up[0][根] 与 dn[0][叶子] 必须指向自己,否则倍增表会在边界处算错。
⚠️
minch 理解错:是"编号最小的儿子",不是"编号最小的后代",也不是"最后一个儿子"。
⚠️
递归建树:n 到 10⁵ 且可能是一条链,递归 DFS 必然爆栈,本题完全可以不建树、只扫父结点数组。
⚠️
倍增层数不够:LOG 至少要 ⌊log₂ n⌋ + 1;n = 10⁵ 时 17 层刚好够,建议直接开到 18 ~ 19。
⚠️
逐步模拟:|a| ≤ n 且 Σk ≤ 10⁵,最坏 10¹⁰ 步,只能拿部分分。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O((n + Σk) log n)
空间复杂度
O(n log n)
预处理
2 × n × LOG ≈ 7.6 × 10⁶ 次赋值
单次移动
≤ ⌈log₂(n + 1)⌉ 次查表

时间怎么算的?

空间都用在哪?

两张表 up、dn 各 LOG × (n + 1) 个 int:2 × 19 × 10⁵ × 4 B ≈ 15 MB;再加父结点、minch 等数组,内存远低于 256 MB。

✅ 预处理约四百万次赋值 + 旅行约两百万次查表,总共不到一千万次基础操作,1 秒时限轻松过。
真正需要小心的不是时间而是细节正确性:两条自环 + 迭代建表,缺一个就可能 WA 或 RE。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「后继函数唯一 + 步数巨大」→ 倍增(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(求儿子编号的最大值),其余倍增结构一行都不用改——因为"后继唯一"这个性质没变。
再想一步:如果改成"移动至任意一个子结点"呢?那时后继不再唯一,"跳 a 步"的结果依赖具体选择,倍增就失效了,得换成别的建模方式(比如 DP 或计数)。识别"后继是否唯一",是判断能不能用倍增的分水岭。)