题解：P13019 [GESP202506 八级] 树上旅行

· · 题解

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

题目链接

转至专栏阅读

解题思路

将题目转化一下，操作 1 就是从一个点向上跳 x 次，操作 2 就是从一个点向下跳 x 次。观察到 x 比较大，如果直接一步一步跳显然会超时。这时我们可以选择倍增。首先预处理出从一个点开始向上和向下跳 2^k 步后会跳到哪里，然后用类似快速幂的方式跳，将 x 二进制分解，如果当前位是 0 就不跳，如果当前位是 1 就跳。时间复杂度 O(k\log n)。

写代码时注意一下边界情况的处理。

参考代码

#include<iostream>
using namespace std;
const int N=1e5+5;
int n,q;
int fa[N][20],ch[N][20];
int get1(int s,int x){
    int nw=0;
    while(x){
        if(x&1) s=fa[s][nw];
        nw++;
        x>>=1;
    }
    return s;
}
int get2(int s,int x){
    int nw=0;
    while(x){
        if(x&1) s=ch[s][nw];
        nw++;
        x>>=1;
    }
    return s;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) ch[i][0]=1e9;
    fa[1][0]=1;//根节点，不往上跳
    for(int i=2,x;i<=n;i++){
        cin>>x;
        ch[x][0]=min(ch[x][0],i);//算出当前节点向下跳一步会跳到哪里
        fa[i][0]=x;//向上跳一步到父亲
    }
    for(int i=1;i<=n;i++)
        if(ch[i][0]==1e9) ch[i][0]=i;//如果该节点是叶子节点，就不往下跳了
    for(int j=1;j<=18;j++)
        for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1],ch[i][j]=ch[ch[i][j-1]][j-1];
    for(int i=1,s,x;i<=q;i++){
        cin>>s>>x;
        for(int j=1,v;j<=x;j++){
            cin>>v;
            if(v>0) s=get1(s,v);
            else s=get2(s,-v);
        }
        cout<<s<<'\n';
    }
    return 0;
}

AC 记录