这题本质上是一个树上第 k 级祖先查询问题。
已知:
你的实验室中诞生了一种新的无性繁殖生物,这种生物每一个都有唯一的父亲(注意,其中有且仅有1号生物的父亲无法追踪到了)。为了研究方便,你定义一个生物的1级祖先即为其父亲,而其k级祖先为k−1级祖先的父亲(k≥2)。例如,2级祖先即为父亲的父亲。现在你想知道一些生物的若干级父亲。
n,q≤50000, 1≤a<i,1≤x,k≤n
第一行两个以空格隔开的正整数n和q。表示生物总数和询问次数
第二行有n−1个由空格隔开的正整数,a2,a3,...an,依次表示2号生物的父亲、3号生物的父亲....i号生物的父亲的编号为ai。其中1号生物的父亲已经无法追踪到了。
接下来q行,每行两个由空格隔开的正整数x,k,表示询问第x号生物的k级祖先。
输出q行,每行依次对应一个询问的答案,即第x号生物的k级祖先。如果无法追踪到该祖先,则输出0
输入
5 3
1 2 3 4
5 1
1 1
5 3
输出
4
0
2
说明
第二次询问1号节点的1级祖先,即父亲,但1号节点的父亲已经无法追踪了,因而输出0