#O1055. 树上第 k 祖先

树上第 k 祖先

题目描述

给定一棵 nn 个点的树,其中 11 号点为根,ii(2≤i≤n2 \le i \le n)号点的父亲为 pip_i,保证 pi<ip_i < i。回答 qq 次询问,每次给出 u,ku, k,求 uu 的第 kk 级祖先(向上走 kk 条边);若不存在输出 0。k=0k=0 时输出 uu 自己。

题目类型

树上倍增

输入格式

第一行两个整数 n,qn, q。

第二行 n−1n-1 个整数 p2,p3,…,pnp_2, p_3, \ldots, p_n(n=1n=1 时该行留空)。

接下来 qq 行,每行两个整数 u,ku, k。

输出格式

共 qq 行,每行一个整数。

样例 #1

样例输入 #1

5 2
1 2 2 4
5 2
3 5

样例输出 #1

2
0

数据规模与约定

数据范围 说明
1≤n,q≤1051 \le n, q \le 10^5 点数与询问数
0≤k≤n0 \le k \le n 上跳步数
  • 倍增表 up[k][u],不存在时记为 0。