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

druzewang · 2025-06-30 21:27:24 · 题解

题意

给定一棵根为 1 号点的树，有 q 次的询问。对于每次，从起点 s 出发，按照指令 a_{i,j}移动：

• 若a_{i,j} > 0:则执行走到父亲节点a_{i,j}次
• 若a_{i,j} < 0:则执行走到编号最小的子节点a_i,_j次

思路

对于这道题目数据较大的题目，可以考虑倍增

定义 fa_{i,j}为节点i向上跳2^j步的位置，则

定义 ms_{i,j}为节点i向下走2^j步的位置，则ms_{i,j} = ms_{ms_{i,j-1},j-1}

对于 fa_{i,0} 以及 ms_{i,0} 可以通过输出以及遍历可以求出

接下来就是喜闻乐见的代码了

代码

#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;
}

后记

求求审核大大过一下