GESP2025年6月认证C++八级( 第三部分编程题（1）树上旅行）

参考程序：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;  // 最大节点数
const int L = 18;       // 因为最多跳 2^17 ≈ 13w > 1e5，所以倍增表最多 18 层
int n, q;              // n个节点，q次询问
int h[N], nx[N];       // 邻接表：h[u]是u的儿子链表头，nx[i]是i的兄弟
int par[L][N];         // par[i][u]: u向上跳2^i步的祖先编号
int son[L][N];         // son[i][u]: u向下跳2^i步，沿最小编号儿子路径// 构建倍增表
void dfs(int u) {// 计算向上跳的倍增表for (int i = 1; i < L; i++)par[i][u] = par[i - 1][par[i - 1][u]];// 初始化son[0][u]为自身son[0][u] = u;// 遍历u的所有儿子，找到编号最小的那个for (int i = h[u]; i; i = nx[i]) {dfs(i);  // 递归构建子树// 若当前u还没有设置下跳路径，或者i比原来的小，就更新if (son[0][u] == u || i < son[0][u])son[0][u] = i;}// 构建向下跳的倍增表for (int i = 1; i < L; i++)son[i][u] = son[i - 1][son[i - 1][u]];
}// 跳路径：从u向上/下跳step步，go表示跳跃表（par或son）
int move(int go[L][N], int u, int step) {for (int i = 0; i < L; i++)if ((step >> i) & 1)  // step包含2^iu = go[i][u];return u;
}
int main() {scanf("%d%d", &n, &q);// 构建树结构for (int i = 2; i <= n; i++) {scanf("%d", &par[0][i]);        // 读入第i个点的父亲nx[i] = h[par[0][i]];           // 建立邻接表（链式前向星）h[par[0][i]] = i;}par[0][1] = 1;  // 根节点指向自己（防越界）dfs(1);  // 构建倍增数组（上跳和下跳）// 处理每次旅行while (q--) {int s, k;scanf("%d%d", &s, &k);  // 起点s，k步while (k--) {int a;scanf("%d", &a);   // 读入第a步操作if (a < 0)         // 向下走s = move(son, s, -a);else               // 向上走s = move(par, s, a);}printf("%d\n", s);  // 输出最终所在节点}return 0;
}