题解:洛谷 P13019 [GESP202506 八级] 树上旅行
发个题解证明我还在...
思路
在从 \(1\) 节点dfs时，用st表倍增，存往上走和往下走即可。
代码
int n, q, dep[N];
int st[2][N][30];//0->down 1->up
vector<int> G[N];
void dfs(int u,int fa){dep[u]=dep[fa]+1;int minx=inf;st[1][u][0]=fa;for(auto v:G[u]){if(v==fa) continue;cmin(minx, v);dfs(v, u);}st[0][u][0]=(minx>n?u:minx);
}
int main(){ioss;cin>>n>>q;for(int i=2,x;i<=n;i++){cin>>x;G[i].push_back(x);G[x].push_back(i);}dfs(1, 1);for(int j=1;j<=20;j++){for(int i=1;i<=n;i++){st[0][i][j]=st[0][st[0][i][j-1]][j-1];st[1][i][j]=st[1][st[1][i][j-1]][j-1];}}for(int i=1, s, k;i<=q;i++){cin>>s>>k;vector<int> a(k+1);for(int j=1;j<=k;j++){cin>>a[j];}for(int j=1;j<=k;j++){if(a[j]>0){if(a[j]>dep[s]||s==1){s=1;continue;}for(int p=0;p<=20;p++){if(a[j]>>p&1){s=st[1][s][p];}}}else{for(int p=0;p<=20;p++){if((-a[j])>>p&1){s=st[0][s][p];}}}}cout<<s<<'\n';}
}