树上旅行(Tree Travel) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    const int LOG = 18;
    vector<vector<int>> up(LOG, vector<int>(n + 1, 1));
    vector<vector<int>> dn(LOG, vector<int>(n + 1, 0));
    vector<int> minChild(n + 1, 0);
    up[0][1] = 1;
    for (int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        up[0][i] = p;
        if (minChild[p] == 0 || i < minChild[p]) {
            minChild[p] = i;
        }
    }
    for (int i = 1; i <= n; ++i) {
        dn[0][i] = (minChild[i] == 0 ? i : minChild[i]);
    }
    for (int k = 1; k < LOG; ++k) {
        for (int i = 1; i <= n; ++i) {
            up[k][i] = up[k - 1][up[k - 1][i]];
            dn[k][i] = dn[k - 1][dn[k - 1][i]];
        }
    }
    for (int i = 0; i < q; ++i) {
        int cur, k;
        cin >> cur >> k;
        for (int j = 0; j < k; ++j) {
            int a;
            cin >> a;
            if (a > 0) {
                int steps = a;
                for (int b = 0; b < LOG; ++b) {
                    if ((steps >> b) & 1) cur = up[b][cur];
                }
            } else {
                int steps = -a;
                for (int b = 0; b < LOG; ++b) {
                    if ((steps >> b) & 1) cur = dn[b][cur];
                }
            }
        }
        cout << cur << "\n";
    }
    return 0;
}