树上旅行

求在一棵 n 个节点的有根树（根节点为 1）上处理 q 次移动查询。移动规则分为两种：向上移动至父节点（若在根节点则原地不动）和向下移动至编号最小的子节点（若在叶节点则原地不动）。每次查询给出起点和一个移动序列，需要依次执行序列中的所有步数，并求出最终到达的节点编号。

June 29, 2025GESP1分钟阅读

题目描述

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

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

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

由于移动次数可能很大，对于第 $i$ 次旅行，旅行中的移动以 $k_i$ 个不为零的整数构成的序列 $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$ 表示。对 $a_{i,j}$ ，若 $a_{i,j} > 0$ 则代表进行 $a_{i,j}$ 次第一种移动；若 $a_{i,j} < 0$ 则代表进行 $-a_{i,j}$ 次第二种移动。根据给出的序列从左至右完成所有移动后，小 A 所在的结点即是旅行的终点。

给定每次旅行的起点与移动序列，请你求出旅行终点的结点编号。

输入格式

第一行，两个正整数 $n, q$ ，分别表示有根树的结点数量，以及旅行次数。

第二行， $n-1$ 个整数 $p_2, p_3, \dots, p_n$ ，其中 $p_i$ 表示结点 $i$ 的父结点编号。

接下来 $2q$ 行中的第 $2i-1$ 行（ $1 \leq i \leq q$ ）包含两个正整数 $s_i, k_i$ ，分别表示第 $i$ 次旅行的起点编号，以及移动序列的长度。第 $2i$ 行包含 $k_i$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$ ，表示移动序列。

输出格式

输出共 $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

输出样例 1

输入样例 2

8 3
5 4 2 1 3 6 6
8 1
8
8 2
8 -8
8 3
8 -8 8

输出样例 2

1
7
1

数据范围

子任务编号	测试点占比	$n$	$q$	$\sum k_i$	特殊性质
$1$	$20\%$	$\leq 100$	$\leq 100$	$\leq 1000$	保证 $a_{i,j}$ 为 $1$ 或 $-1$
$2$	$20\%$	$\leq 10^4$	$\leq 10^4$	$\leq 4 \times 10^4$	仅包含第一种移动
$3$	$20\%$	$\leq 10^4$	$\leq 10^4$	$\leq 4 \times 10^4$	仅包含第二种移动
$4$	$40\%$	$\leq 10^5$	$\leq 2 \times 10^4$	$\leq 10^5$	-

对于所有测试点，保证： $1 \leq n \leq 10^5$ 、 $1 \leq q \leq 2 \times 10^4$ 、 $1 \leq p_i \leq n$ 、 $1 \leq s_i \leq n$ 、 $k_i \geq 1$ 且 $\sum k_i \leq 10^5$ 、 $1 \leq |a_{i,j}| \leq n$ 。

题目中的两种移动规则具有非常明确的唯一确定性：

向上移动：每个节点的父节点是唯一确定的（根节点指向自身）；
向下移动：每个节点编号最小的子节点也是唯一确定的（叶节点指向自身）。

由于这两种移动都相当于在两条固定的“单向链”上前进，若单次一步步模拟移动，面对大步数时会超时。因此，我们可以预处理出每个节点向上和向下走 $2^i$ 步所能到达的节点，建立两套倍增表。对于每次给定的移动步数 $a_{i,j}$ ，将其进行二进制拆分，即可在 $\mathcal{O}(\log n)$ 时间内直接“跳”到目标节点。

从当前节点向上移动 $x$ 步到其第 $x$ 级祖先。
如果移动次数超过当前节点到根节点 $1$ 的距离，则停留在根节点 $1$ 。
可以使用经典的树上倍增表 fa[u][i]（表示节点 $u$ 的第 $2^i$ 级祖先）在 $\mathcal{O}(\log n)$ 时间内完成。

从当前节点向下移动，每次都选择子节点中编号最小的那个。
如果到达叶子节点，则停止移动。
由于每个节点 $u$ 的“最小子节点”是唯一固定的（记为 min_child[u]），这构成了另一条向下的单向链。
同样可以使用倍增表 down[u][i]（表示沿最小子节点向下走 $2^i$ 步到达的节点）在 $\mathcal{O}(\log n)$ 时间内完成。若中间到达叶子节点，倍增表记录为叶子节点本身即可。

预处理 min_child

遍历树的所有节点，对每个非叶节点找到其所有子节点中编号最小的一个，记为 min_child[u]。如果 $u$ 是叶节点，则 min_child[u] = u。
构建倍增数组

向上倍增数组 fa[u][i]：
- 初始 fa[u][0] = p[u]，fa[1][0] = 1。
- 转移方程：fa[u][i] = fa[fa[u][i-1]][i-1]。
向下倍增数组 down[u][i]：
- 初始 down[u][0] = min_child[u]。
- 转移方程：down[u][i] = down[down[u][i-1]][i-1]。
回答查询

对于每次旅行的序列 $a_i$ ：
- 若 $a_{i,j} > 0$ ：利用 fa 数组从当前节点向上跳 $a_{i,j}$ 步。
- 若 $a_{i,j} < 0$ ：利用 down 数组从当前节点向下跳 $-a_{i,j}$ 步。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
const int LOGN = 18; // log2(100005) < 18

int p[MAXN];
int min_child[MAXN];
int fa[MAXN][LOGN];
int down[MAXN][LOGN];

int main() {
    // 优化 I/O 性能
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    // 初始化 min_child 数组（默认为 0，表示没有子节点）
    for (int i = 1; i <= n; ++i) {
        min_child[i] = 0;
    }

    // 读取父节点，并预处理每个节点的“最小子节点”
    for (int i = 2; i <= n; ++i) {
        cin >> p[i];
        int parent = p[i];
        if (min_child[parent] == 0 || i < min_child[parent]) {
            min_child[parent] = i;
        }
    }

    // 预处理叶子节点和根节点的边缘情况
    p[1] = 1; // 根节点 1 的父节点指向自己，实现停留在根节点的效果
    for (int i = 1; i <= n; ++i) {
        if (min_child[i] == 0) {
            min_child[i] = i; // 叶子节点没有子节点，指向自己，实现停留在叶节点的效果
        }
    }

    // 构建 2^0 步的倍增基底
    for (int i = 1; i <= n; ++i) {
        fa[i][0] = p[i];
        down[i][0] = min_child[i];
    }

    // 构建倍增表 fa 和 down
    for (int j = 1; j < LOGN; ++j) {
        for (int i = 1; i <= n; ++i) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
            down[i][j] = down[down[i][j - 1]][j - 1];
        }
    }

    // 处理 q 次旅行查询
    while (q--) {
        int u, k;
        cin >> u >> k;

        for (int i = 0; i < k; ++i) {
            int a;
            cin >> a;

            if (a > 0) {
                // 向上跳 a 步
                for (int j = LOGN - 1; j >= 0; --j) {
                    if ((a >> j) & 1) {
                        u = fa[u][j];
                    }
                }
            } else if (a < 0) {
                // 向下跳 -a 步
                int steps = -a;
                for (int j = LOGN - 1; j >= 0; --j) {
                    if ((steps >> j) & 1) {
                        u = down[u][j];
                    }
                }
            }
        }

        cout << u << "\n";
    }

    return 0;
}

时间复杂度： 预处理倍增表为 $\mathcal{O}(n \log n)$ ；处理所有查询为 $\mathcal{O}((\sum k_i) \log n)$ 。总时间复杂度满足 $1.00\text{s}$ 的要求。
空间复杂度： $\mathcal{O}(n \log n)$ ，空间限制为 $512\text{MB}$ ，完全够用。

算法思路

第一种移动（向上跳祖先）：

第二种移动（向下沿最小子节点走）：

具体步骤

参考代码

复杂度分析