专栏文章

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

ddruzewang
P13019题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip0caoq
此快照首次捕获于
2025/12/03 04:05
3 个月前
此快照最后确认于
2025/12/03 04:05
3 个月前
查看原文

题意

给定一棵根为 1 号点的树，有 q 次的询问。对于每次，从起点 s 出发，按照指令 ai,ja_{i,j}移动：
  • 若ai,j>0a_{i,j} > 0:则执行走到父亲节点ai,ja_{i,j}次
  • 若ai,j<0a_{i,j} < 0:则执行走到编号最小的子节点ai,ja_i,_j次

思路

对于这道题目数据较大的题目，可以考虑倍增
定义 fai,jfa_{i,j}为节点i向上跳2j2^j步的位置，则 fai,j=fafai,j−1,j−1fa_{i,j} = fa_{fa_{i,j-1},j-1}
定义 msi,jms_{i,j}为节点i向下走2j2^j步的位置，则msi,j=msmsi,j−1,j−1ms_{i,j} = ms_{ms_{i,j-1},j-1}
对于 fai,0fa_{i,0} 以及 msi,0ms_{i,0} 可以通过输出以及遍历可以求出
接下来就是喜闻乐见的代码了

代码

CPP
#include<bits/stdc++.h>
using namespace std;

int n,logn,q,s,k,fa[100005][30],ms[100005][30];
vector<int>e[100005];



int main(){
    scanf("%d%d",&n,&q);
    fa[1][0] = 1;
    for (int i = 2;i <= n;i++){
        cin >> fa[i][0];
        e[fa[i][0]].push_back(i);
    }
    logn = log2(n);
    for (int j = 1;j <= logn;j++) for (int i = 1;i <= n;i++)
            fa[i][j] = fa[fa[i][j-1]][j-1];
    for (int i = 1;i <= n;i++){
        int minn=i,sz=e[i].size();
        for (int j = 0;j < sz;j++)
            if (minn == i || minn > e[i][j]) minn = e[i][j];
        ms[i][0] = minn;
    }
    for (int j = 1;j <= logn;j++) for (int i = 1;i <= n;i++) 
        ms[i][j]=ms[ms[i][j-1]][j-1];
    while (q--){
        scanf("%d%d",&s,&k);
        while (k--){
            int ai;scanf("%d",&ai);
            if (ai > 0){
                for (int i = 0;i <= logn;i++)
                    if (ai & (1 << i)) s = fa[s][i];
            }
            if (ai < 0){
                ai = -ai;
                for (int i = 0;i <= logn;i++)
                    if (ai & (1 << i)) s = ms[s][i];
            }
        }
        printf("%d\n",s);
    }
    return 0;
}

后记

求求审核大大过一下

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...