P4639.第1题-祖先
题目内容
你的实验室中诞生了一种新的无性繁殖生物，这种生物每一个都有唯一的父亲(注意，其中有且仅有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
样例1
输入
5 3
1 2 3 4
5 1
1 1
5 3
输出
4
0
2
说明
第二次询问1号节点的1级祖先，即父亲，但1号节点的父亲已经无法追踪了，因而输出0
