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

题意

给定一棵有根树（根为 1 号点），有

q

次查询。每次从某个起点

s

出发，按照指令

a_{i,j}

移动：

$a_{i,j}>0$ ：向上走 $a_{i,j}$ 步（即走到 $a_{i,j}$ 级祖先）。
$a_{i,j}<0$ ：向下走 $a_{i,j}$ 步，每一步都选择当前点所有子节点中编号最小的那个继续走。

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

思路

注意到

\sum a_{i,j}

最大可以到

2 \times 10^9

，考虑倍增。

设

f_{x,j}

表示结点

x

向上跳

2^j

步后的位置，则：

f_{x,j}=f_{f_{x,j-1},j-1}

设

s_{x,j}

表示结点

x

向下跳

2^j

步后的位置，则：

s_{x,j}=s_{s_{x,j-1},j-1}

为了具体实现，我们可以先建一棵树（这里叫 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;
}

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

文章操作

题意

思路

代码

相关推荐

评论

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