A2098 [GESP-8.2506.T1] 树上旅行

#include <bits/stdc++.h>
using namespace std;

// 两种移动：
//   1) 往父结点走（正数 a），到根就停；
//   2) 往「编号最小的子结点」走（负数 a），到叶子就停。
// 两种移动各自是一条固定链，用倍增一次跳 2^j 步。

const int LOG = 18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;

    vector<int> parent(n + 1, 0);
    vector<vector<int>> child(n + 1);
    for (int i = 2; i <= n; i++) {
        cin >> parent[i];
        child[parent[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) sort(child[i].begin(), child[i].end());

    vector<vector<int>> up(LOG, vector<int>(n + 1));
    vector<vector<int>> dn(LOG, vector<int>(n + 1));
    for (int v = 1; v <= n; v++) {
        up[0][v] = parent[v] ? parent[v] : v;      // 根的父结点是它自己
        dn[0][v] = child[v].empty() ? v : child[v][0];
    }
    for (int b = 1; b < LOG; b++)
        for (int v = 1; v <= n; v++) {
            up[b][v] = up[b - 1][up[b - 1][v]];
            dn[b][v] = dn[b - 1][dn[b - 1][v]];
        }

    while (q--) {
        int s, k;
        cin >> s >> k;
        int cur = s;
        for (int i = 0; i < k; i++) {
            long long a;
            cin >> a;
            if (a > 0) {
                int step = (int)a;
                for (int b = 0; b < LOG; b++)
                    if ((step >> b) & 1) cur = up[b][cur];
            } else {
                int step = (int)(-a);
                for (int b = 0; b < LOG; b++)
                    if ((step >> b) & 1) cur = dn[b][cur];
            }
        }
        cout << cur << "\n";
    }
    return 0;
}