G8013 [GESP202506 八级] 树上旅行 题解

知识点：倍增、树上跳跃、多查询。

解题思路

为每点选编号最小的孩子，无孩子时指向自己；分别建立父方向up和最小孩子方向down两张倍增表。每个正负移动指令拆成二进制快速跳跃。

为什么正确

两方向都构成确定的后继函数，倍增表复合2^j次移动，二进制拆分可准确执行任意步数。

易错点

正指令向父，负指令向最小编号孩子；根向上、叶向下要停在自身，不能越界到0。

复杂度

预处理O(n log n)，所有指令共K条时O(K log n)，空间O(n log n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<int>p(n+1,1),ch(n+1);
    for(int i=1;i<=n;i++)ch[i]=i;
    for(int i=2;i<=n;i++) {
        cin>>p[i];
        if(ch[p[i]]==p[i])ch[p[i]]=i;
        else ch[p[i]]=min(ch[p[i]],i);
    }
    vector<vector<int>>up(18,p),down(18,ch);
    for(int k=1;k<18;k++)for(int i=1;i<=n;i++) {
        up[k][i]=up[k-1][up[k-1][i]];
        down[k][i]=down[k-1][down[k-1][i]];
    }
    while(q--) {
        int s,k;
        cin>>s>>k;
        while(k--) {
            int a;
            cin>>a;
            auto &tab=a>0?up:down;
            a=abs(a);
            for(int j=0;j<18;j++)if(a>>j&1)s=tab[j][s];
        }
        cout<<s<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用16个自行生成的测试点。