首先，我們來分析一下題目中給出的兩種移動方法：

1. 移動至當前結點的父結點。特殊地，如果當前位于根結點，則不進行移動；
2. 移動至當前結點的所有子結點中編號最小的結點。特殊地，如果當前位于葉子結點，則不進行移動。

預處理

不難發現，對于每個節點 \(i\) 來說，它最高能達到的節點一定是根節點 \(1\)，最低能達到的節點同樣是固定的。那么，我們不妨預處理一下 \(i\) 號節點的第 \(2^j\) 級祖先 \(f[i][j]\) 與其第 \(2^j\) 級子節點 \(son[i][j]\)，當然 \(i\) 號節點的第 \(2^j\) 級子節點最多可能有 \(2^{j+1}\) 個，我們不可能維護 \(i\) 號節點的所有第 \(2^j\) 級子節點，所以我們只維護 \(i\) 號節點在第 \(2\) 種移動方式下會移動到的子節點，\(son[i][0]\) 維護的是 \(i\) 號節點的最小的一級子節點，\(son[i][1]\) 維護的是 \(son[i][0]\) 號節點的最小的一級子節點，\(son[i][2]\) 維護的是 \(son[i][1]\) 號節點的最小的二級子節點，以此類推

處理移動

接下來，讓我們來處理移動，我們以向上移動 \(a_{i,j}\) 次為例，我們將當前位于節點 \(s\) 的深度 \(d[s]\) 減 \(a_{i,j}\),特判 \(d[s]\) 是否等于 \(1\),如果等于 \(1\),我們就將 \(d[s]\) 與 \(s\) 賦值為 \(1\),否則通過 \(f[s]\) 數組將 \(s\) 跳到這個深度。至于向下跳，我們只需注意將跳至 \(1\) 號根節點的特判改為跳至 \(son[s][18]\) 號最底層節點的特判，為什么 \(son[s][18]\) 就是最底層節點呢？因為我們可以將葉節點的 \(son[s][0]\) 記為 \(s\) 自己，這樣由于 \(2^{18}=262144>100000=n\),那么在遞歸更新中 \(son[i][18]\) 一定會更新為 \(i\) 號節點的最底層節點。

最后的時間復雜度為 \(O(n+\log n(n+\displaystyle\sum^q_{i=1} k_i))\)

沒想明白為什么不小心把向下跳更新 \(s\) 與向上跳更新 \(s\) 同時寫成了向上跳更新 \(s\) 的函數后也是100pts（離譜）

code

#include<bits/stdc++.h>
using namespace std;
int n,q,f[100005][25],son[100005][25],d[100005],s,k;
priority_queue<int,vector<int>,greater<int> >e[100005];//通過優先隊列維護小的子節點在前
void init(int x){//預處理
	for(int i=1;i<=18;i++)
		f[x][i]=f[f[x][i-1]][i-1];
	bool f=true;
	int id;
	while(!e[x].empty()){
		if(f){
			son[x][0]=e[x].top();
			f=false;
		}
		d[e[x].top()]=d[x]+1;
		init(e[x].top());
		e[x].pop();
	}
	if(!son[x][0])
		son[x][0]=x;
	for(int i=1;i<=18;i++)
		son[x][i]=son[son[x][i-1]][i-1];
}
int down(int st,int de){
	for(int i=18;i>=0;i--){
		if(d[son[st][i]]<=de)
			st=son[st][i];
	}
	return st;
}
int up(int st,int de){
	for(int i=18;i>=0;i--){
		if(d[f[st][i]]>=de)
			st=f[st][i];
	}
	return st;
}
int main(){
	cin>>n>>q;
	for(int i=0;i<n-1;i++){
		int x;
		cin>>x;
		e[x].push(i+2);
		f[i+2][0]=x;
	}
	d[1]=1;
	init(1);
	for(int i=0;i<q;i++){
		cin>>s>>k;
		int x,p=d[s];
		for(int j=0;j<k;j++){
			cin>>x;
			if(x<0){//向下跳 
				p-=x;
				if(p>=d[son[s][18]])
					p=d[son[s][18]];
				s=down(s,p); 
			}
			if(x>0){//向上跳 
				p-=x;
				if(p<=1){
					s=1;
					p=1;
				}
				s=up(s,p);
			}
			
		}
		cout<<down(s,p)<<endl;
	}
	return 0;
}