[Ynoi2000] tmostnrq
题目描述
给定 $n$ 个顶点的树,顶点编号为 $1,\dots,n$,给定长度 $n_0$ 的序列 $a_1,\dots,a_{n_0}$,共 $m$ 次查询,每次查询给定 $l,r,x$,问树的顶点 $x$,依次向 $a_l,\dots,a_r$ 移动一步,到达的顶点。
若 $x=y$,则从顶点 $x$ 向 $y$ 移动一步到达 $x$,否则到达与 $x$ 在树上相邻且距离 $y$ 最近的位置。
输入输出格式
输入格式
第一行三个整数 $n,n_0,m$;
接下来一行 $n-1$ 个整数依次表示 $f_2,\dots,f_n$,其中 $f_i$ 是顶点 $i$ 的父亲,$1$ 为根;
接下来一行 $n_0$ 个整数,依次表示 $a_1,\dots,a_{n_0}$;
接下来 $m$ 行,每行三个整数 $l,r,x$ 表示一次查询。
输出格式
共 $m$ 行,依次为每次查询的答案。
输入输出样例
输入样例 #1
5 4 3
1 1 3 3
5 2 2 3
3 4 5
1 3 4
1 2 1
输出样例 #1
3
2
1
说明
Idea:Ynoi,Solution:zhoukangyang&ccz181078,Code:zhoukangyang,Data:ccz181078
对于 $100\%$ 的数据,满足 $1\le n,n_0,m\le 10^6$;