题目描述
给定一棵有 n 个结点的 有根树，结点依次以 1,2,…,n 编号，其中根结点的编号为 1。
小 A 计划在这棵有根树上进行 q 次旅行。在第 i 次旅行中，小 A 首先选定结点 si 作为起点，并移动若干次。移动分为以下两种：
- 移动至当前结点的父结点。特殊地，如果当前位于根结点，则不进行移动。
- 移动至当前结点的所有子结点中编号最小的结点。特殊地，如果当前位于叶子结点，则不进行移动。
由于移动次数可能很大，对于第 i 次旅行，旅行中的移动以 ki 个不为零的整数构成的序列 ai,1,ai,2,…,ai,ki 表示。对 ai,j，若 ai,j>0 则代表进行 ai,j 次第一种移动；若 ai,j<0 则代表进行 −ai,j 次第二种移动。根据给出的序列从左至右完成所有移动后，小 A 所在的结点即是旅行的终点。
给定每次旅行的起点与移动序列，请你求出旅行终点的结点编号。
输入格式
第一行，两个正整数 n,q，分别表示有根树的结点数量，以及旅行次数。
第二行，n−1 个整数 p2,p3,…,pn，其中 pi 表示结点 i 的父结点编号。
接下来 2q 行中的第 2i−1 行（1≤i≤q）包含两个正整数 si,ki，分别表示第 i 次旅行的起点编号，以及移动序列的长度。第 2i 行包含 ki 个整数 ai,1,ai,2,…,ai,ki，表示移动序列。
输出格式
输出共 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
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
输出 #2
1 7 1
说明/提示
| 子任务编号 | 测试点占比 | n | q | ∑ki | 特殊性质 |
|---|---|---|---|---|---|
| 1 | 20% | ≤100 | ≤100 | ≤1000 | 保证 ai,j 为 1 或 −1 |
| 2 | 20% | ≤104 | ≤104 | ≤4×104 | 仅包含第一种移动 |
| 3 | 20% | ≤104 | ≤104 | ≤4×104 | 仅包含第二种移动 |
| 4 | 40% | ≤105 | ≤2×104 | ≤105 | - |
对于所有测试点，保证：
- 1≤n≤105
- 1≤q≤2×104
- 1≤pi≤n
- 1≤si≤n
- ki≥1 且 ∑ki≤105
- 1≤∣ai,j∣≤n
题目大意：
给定一棵有根树（根为1号点），有 q 次查询。每次从某个起点 s 出发，按照指令 ai,j 移动：ai,j>0：向上走 ai,j 步（即走到 ai,j 级祖先）。ai,j<0：向下走 ai,j 步，每一步都选择当前点所有子节点中编号最小的那个继续走。输出每次操作后停在的最终结点编号。
考纲知识点：倍增LCA
解析：
将题目转化一下，操作1就是从一个点向上跳x次，操作2就是从一个点向下跳x次。观察到x比较大，如果直接一步一步跳显然会超时。这时我们可以选择倍增。首先预处理出从一个点开始向上和向下跳2k步后会跳到哪里，然后用类似快速幂的方式跳，将x二进制分解，如果当前位是0就不跳，如果当前位是1就跳。时间复杂度O(klogn)。
写代码时注意一下边界情况的处理。
参考程序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int LOG = 20; // 足够处理1e5规模的树
int n, q;
int fa[N][LOG]; // 向上跳2^j步到达的节点
int ch[N][LOG]; // 向下跳2^j步到达的节点（每次跳向最小子节点）
// 向上跳x步
int get_up(int s, int x) {
for (int j = 0; j < LOG; ++j) {
if (x & (1 << j)) {
s = fa[s][j];
}
}
return s;
}
// 向下跳x步（每次跳向最小子节点）
int get_down(int s, int x) {
for (int j = 0; j < LOG; ++j) {
if (x & (1 << j)) {
s = ch[s][j];
}
}
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
// 初始化：每个节点的子节点先设为自身（表示无法向下跳）
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < LOG; ++j) {
ch[i][j] = i;
}
}
// 根节点的父节点设为自身（表示无法向上跳）
for (int j = 0; j < LOG; ++j) {
fa[1][j] = 1;
}
// 存储每个节点的子节点，用于后续排序找到最小子节点
vector<int> children[N];
// 读取父节点信息
for (int i = 2; i <= n; ++i) {
int p;
cin >> p;
fa[i][0] = p; // 向上跳1步(2^0)到达父节点
children[p].push_back(i);
}
// 对每个节点的子节点排序，找到编号最小的子节点
for (int i = 1; i <= n; ++i) {
if (!children[i].empty()) {
sort(children[i].begin(), children[i].end());
ch[i][0] = children[i][0]; // 向下跳1步(2^0)到达最小子节点
}
}
// 预处理倍增表
for (int j = 1; j < LOG; ++j) {
for (int i = 1; i <= n; ++i) {
fa[i][j] = fa[fa[i][j-1]][j-1]; // 向上跳2^j步 = 先跳2^(j-1)步，再跳2^(j-1)步
ch[i][j] = ch[ch[i][j-1]][j-1]; // 向下跳2^j步 = 先跳2^(j-1)步，再跳2^(j-1)步
}
}
// 处理每次查询
while (q--) {
int s, k;
cin >> s >> k;
for (int i = 0; i < k; ++i) {
int a;
cin >> a;
if (a > 0) {
// 向上移动a次
s = get_up(s, a);
} else {
// 向下移动|a|次
s = get_down(s, -a);
}
}
cout << s << '\n';
}
return 0;
}