A27134. 树上旅行
填空题
困难
知识点
题目描述
树上旅行
题目描述
给定一棵有n个结点的有根树，结点依次以1,2,...,n编号，其中根结点的编号为 1。
小A 计划在这棵有根树上进行q次旅行。在第i次旅行中，小A首先会选定结点si作为起点，并移动若干次。移动分为以下两种:
1.移动至当前结点的父结点。特殊地，如果当前位于根结点，则不进行移动。
2.移动至当前结点的所有子结点中编号最小的结点。特殊地，如果当前位于叶子结点，则不进行移动。
由于移动次数可能很大，对于第i次旅行，旅行中的移动将以 ki个不为零的整数构成的序列 ai,1,ai,2,……,ai.k 表示。对于 ai,j，若 ai,j>0则代表进行ai,j次第一种移动;若 ai,j<0则代表进行 -ai,j次第二种移动。根据给出的序列从左至右完成所有移动后，小A所在的结点即是旅行的终点。
给定每次旅行的起点与移动序列，请你求出旅行终点的结点编号。
输入格式
第一行，两个正整数n,q，分别表示有根树的结点数量，以及旅行次数。
第二行，n-1个整数 p2,p3,...,pn，其中pi表示结点i的父结点编号。
接下来 2q 行中的第 2i-1行(1≤i≤q)包含两个正整数 si,ki，分别表示第i次旅行的起点编号，以及移动序列的长度。第2i 行包含 ki个整数 ai,1,ai,2,·..,ai,ki，表示移动序列。
输出格式
输出共q行，第i行包含一个整数，表示第i次旅行终点的结点编号。
样例
输入样例1
5 4
1 1 2 2
3 3
1 -1 -1
2 5
1 -1 1 -1 1
5 8
1 1 1 -1 -1 -1 -1 -1
5 3
-1 -1 1输出样例1
4
1
4
2输入样例 2
8 3
5 4 2 1 3 6 6
8 1
8
8 2
8 -8
8 3
8 -8 8输出样例2
1
7
1数据范围
对于所有测试点，保证1≤n≤105,1≤q≤2x104,1≤pi≤n,1≤si≤n,ki≥1且∑ki≤105,l ≤ |ai,j|≤ n。
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5 +5;
const int L=18;
int n，q；
int h[N], nx[N];
int par[L][N],son[L][N];
void dfs(int u){
for(int i= 1; i <L; i++)
par[i][u]=par[i -1][par[i - 1][u]];
son[0][u]= u;
for(int i= h[u]; i; i= nx[i]){
dfs(i);
if(son[0][u]==u||i< son[0][u])
son[e][u]= i;
}
for(int i=1; i <L; i++)
son[i][u]=son[i-1][son[i - 1][u]];
}
int move(int go[L][N],int u, int step){
for(int i=0;i<L; i++)
if((step >>i)& 1)
u= go[i][u];
return u;
}
int main(){
scanf("%d%d"，&n,&q);
for(int i=2;i<= n; i++){
scanf("%d"，&par[0][i]);
nx[i]= h[par[o][i]];
h[par[e][i]] = i;
}
par[0][1]= 1;
dfs(1);
while(q--){
int s, k;
scanf("%d%d"，&s,&k);
while(k--){
int a;
scanf("%d"，&a);
if(a< 0)
s=move(son,s,-a);
else
s= move(par,s, a);
}
printf("%d\n"，s);
}
return 0;
}
上一题
下一题