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

songge888 · 2025-06-30 16:52:00 · 题解

题意

给定一棵有根树（根为 1 号点），有 q 次查询。每次从某个起点 s 出发，按照指令 a_{i,j} 移动：

输出每次操作后停在的最终结点编号。

思路

注意到 \sum a_{i,j} 最大可以到 2 \times 10^9，考虑倍增。

设 f_{x,j} 表示结点 x 向上跳 2^j 步后的位置，则：

设 s_{x,j} 表示结点 x 向下跳 2^j 步后的位置，则：

为了具体实现，我们可以先建一棵树（这里叫 g）。

然后对于每个点 u，对所有 u 的子节点 v 从小到大排序。

这样 g[u][0] 便是节点 u 向下走的字节点。

之后分别向下和向上倍增即可。

代码

#include<bits/stdc++.h>
#define int long long
#define double long double
#define bug cout<<"___sgge888___"<<'\n';
using namespace std;
int n,m;
int f[100005][20];
int s[100005][20];
vector<int>g[100005];
int dep[100005];
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    if(!g[u].empty()){
        s[u][0]=g[u][0];
    }
    else{
        s[u][0]=u;
    }
    for(auto v:g[u]){
        dfs(v,u);
    }
}
void init(){
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            if(f[i][j-1]!=0){
                f[i][j]=f[f[i][j-1]][j-1];
            }
        }
    }
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            s[i][j]=s[s[i][j-1]][j-1];
        }
    }
}
int up(int u,int k){
    if(u==1){
        return 1;
    }
    int dis=dep[u]-1;
    if(k>=dis){
        return 1;
    }
    for(int i=0;i<20;i++){
        if((k>>i)&1){
            u=f[u][i];
        }
    }
    return u;
}
int down(int u,int k){
    for(int i=0;i<20;i++){
        if((k>>i)&1){
            u=s[u][i];
        }
    }
    return u;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=0;j<20;j++){
            s[i][j]=i;
        }
    }
    f[1][0]=0;
    for(int i=2;i<=n;i++){
        int p;
        cin>>p;
        f[i][0]=p;
        g[p].push_back(i);
    }
    for(int i=1;i<=n;i++){
        sort(g[i].begin(),g[i].end());
    }
    dfs(1,0);
    init();
    for(int i=1;i<=m;i++){
        int u,k;
        cin>>u>>k;
        int ans=u;
        for(int j=1;j<=k;j++){
            int x;
            cin>>x;
            if(x>0){
                ans=up(ans,x);
            }
            else{
                x=-x;
                ans=down(ans,x);
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}