树上旅行 题解

题目分析

我们有一棵以 1 为根的树，结点数 n 次旅行 q 次。每次旅行从起点 s 出发，按照给定的移动序列依次移动。移动有两种：

1. 向上：移动到父结点（根结点则不动）。
2. 向下：移动到子结点中编号最小的那个（叶子则不动）。

移动序列中，正数表示向上移动的次数，负数绝对值表示向下移动的次数。步数可能很大（最大可达 n），旅行序列的总长度 (\sum k_i \le 10^5)。我们需要对每次旅行求出最终所在的结点。

解题思路

若直接模拟每一步，单步移动 O(1)，但一次移动指令可能包含 O(n) 步，会超时。题目数据范围提示我们：树的大小和总指令数均不超过 (10^5)，因此可以对每个指令用 倍增（二进制拆分） 加速移动，将单次移动的复杂度降至 O(log n)。

具体需要预处理两类倍增表：

• par[j][u]：从结点 u 向上移动 (2^j) 步到达的结点。
• son[j][u]：从结点 u 连续进行 (2^j) 次“向下走到最小编号子结点”的移动后到达的结点。

这两种移动都是确定性的，因此我们可以用类似 LCA 的倍增方法预处理。

算法说明

1. 建树与找最小编号子结点

输入给出了每个结点的父结点，父结点确定后，子结点关系也随之确定。我们为每个结点拉一条邻接表，同时找出它编号最小的子结点作为 son[0][u]。若没有子结点（叶子），则 son[0][u] = u 表示原地不动。

2. 倍增预处理

对于向上移动：

• par[0][u] 已知。
• 根结点的 par[0][1] 设为 1，保证向上越界的结点原地不动。
• 倍增递推：par[j][u] = par[j-1][ par[j-1][u] ]。

对于向下移动（找最小编号子结点）：

• son[0][u] 已经得到。
• 倍增递推：son[j][u] = son[j-1][ son[j-1][u] ]。
• 由于叶子结点的 son[0][u] == u，后续倍增也会停留在原地，符合题意。

这里的倍增层数 L 取 (\lceil \log_2 n \rceil)，本题中取 18 足够。

3. 处理移动指令

对于步数为 step 的向上指令，利用 par 表进行二进制拆分：

cpp
复制
1for (int i = 0; i < L; i++)
2    if ((step >> i) & 1)
3        u = par[i][u];

向下指令同理，使用 son 表。

4. 时间复杂度

• 预处理：每个结点和每个倍增层 O(n log n)。
• 所有询问：指令总长度 (\sum k_i \le 10^5)，每条指令倍增 O(log n)，总 O(∑k_i log n)。

极限数据可在时限内轻松通过。

参考代码

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5const int N = 1e5 + 5;
6const int L = 18;
7
8int n, q;
9int h[N], nx[N];          // 邻接表
10int par[L][N], son[L][N]; // 倍增表
11
12// 深度优先遍历，预处理倍增表
13void dfs(int u) {
14    // 向上倍增
15    for (int i = 1; i < L; i++)
16        par[i][u] = par[i - 1][par[i - 1][u]];
17
18    // 向下倍增初始化：选择编号最小的子结点
19    son[0][u] = u; // 叶子时原地不动
20    for (int i = h[u]; i; i = nx[i]) {
21        dfs(i);
22        if (son[0][u] == u || i < son[0][u])
23            son[0][u] = i;
24    }
25    // 向下倍增递推
26    for (int i = 1; i < L; i++)
27        son[i][u] = son[i - 1][son[i - 1][u]];
28}
29
30// 利用倍增表移动 step 步
31int move(int go[L][N], int u, int step) {
32    for (int i = 0; i < L; i++)
33        if ((step >> i) & 1)
34            u = go[i][u];
35    return u;
36}
37
38int main() {
39    scanf("%d%d", &n, &q);
40    // 读入父结点，建立邻接表
41    for (int i = 2; i <= n; i++) {
42        scanf("%d", &par[0][i]);
43        nx[i] = h[par[0][i]];
44        h[par[0][i]] = i;
45    }
46    par[0][1] = 1; // 根结点的父亲设为自己
47    dfs(1);
48
49    while (q--) {
50        int s, k;
51        scanf("%d%d", &s, &k);
52        while (k--) {
53            int a;
54            scanf("%d", &a);
55            if (a < 0)          // 向下移动
56                s = move(son, s, -a);
57            else                // 向上移动
58                s = move(par, s, a);
59        }
60        printf("%d\n", s);
61    }
62    return 0;
63}

代码解释

• h[u] 是邻接表表头，nx[i] 是下一条边的编号。建树时子结点插入链表头部，但不影响后续选择最小编号子结点，因为我们遍历链表取出的是实际编号 i。
• son[0][u] 初始为 u（叶子不动），遍历子结点时若发现编号更小则更新，最终存的就是最小编号子结点。
• move 函数根据二进制拆分实现 O(log step) 的跳转。
• 每次旅行依次读取指令，正数向上，负数向下，依次更新当前位置即可。

这样我们就用倍增技巧高效解决了本题，避免了每次移动的单步模拟。