专栏文章

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

XXCDRF
P13019题解参与者 2已保存评论 3

文章操作

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

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

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

题目链接
转至专栏阅读

解题思路

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

参考代码

CPP
#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 记录

评论

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

正在加载评论...